반응형 정렬3 [Java] 병합 정렬 (Merge Sort) 구현 병합 정렬(Merge Sort)은 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할하고 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부 분리스트를 생성하는 알고리즘입니다. 시간 복잡도는 O(n log n)이며, 항상 두 부분리스트로 분할하여 병합하기 때문에 시간 복잡도가 O(n log n)으로 유지됩니다. 다만, 정렬 중 추가적으로 필요한 배열 공간을 사용하므로 메모리 사용량이 많습니다. 또한, 데이터가 많을 경우 상대적으로 시간이 많이 소요됩니다. 흔히 사용되는 2-way 방식으로 구현하였으며, 과정은 다음과 같습니다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 분할 : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정.. 2021. 10. 31. [Java] 거품 정렬 (Bubble Sort) 구현 거품 정렬(Bubble Sort)은 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 시간 복잡도는 O(n2)이며 구현이 간단하다는 장점이 있습니다. 하지만, 다른 정렬 알고리즘에 비해 많은 시간을 소비합니다. Java Code import java.io.*; import java.util.Arrays; /** * 거품 정렬 */ public class BubbleSort { public static void main(String[] args) throws IOException { BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int[] arr = {5, 4, 3, 2, 1}; bw.write("정렬 전 : " +.. 2021. 10. 30. [Java] 삽입 정렬 (Insertion Sort) 구현 삽입 정렬(Insertion Sort)은 배열의 두 번째 요소부터 차례대로 자신의 앞의 요소들과 비교하여 자신이 들어갈 위치를 찾고 삽입함으로써 정렬하는 알고리즘입니다. 시간 복잡도는 O(n2)이며, 구현이 간단하고 거의 정렬된 경우 시간 복잡도가 O(n)에 가까운 장점이 있습니다. Java Code import java.util.Arrays; public class MySort { public static void main(String[] args) throws IOException { int[] arr = createArr(); System.out.println("[삽입 정렬] 정렬 전 => " + Arrays.toString(arr)); insertionSort(arr); System.out.pri.. 2021. 10. 29. 이전 1 다음 반응형
