pinevienna blog

합병 정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬하는 작업을 반복하는 알고리즘이다. n개를 log n번 돌리기 때문에 최선, 평균, 최악 모두 O(n log n)의 시간복잡도를 가진다. 1) 배열을 반으로 나눈다. 2) 각 파티션이 두 개의 요소를 가질 때 까지 계속 반으로 나눠준다. 3) 두 개의 요소를 비교하여 더 작은 요소가 앞으로 오도록 한다. 4) 두 개의 파티션을 비교하여 더 작은 요소가 앞으로 오도록 병합한다. 5) 4 반복 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 private static void mergeSo..

퀵 정렬은 분할 정복 알고리즘 중 하나이며 이름처럼 정렬 속도가 매우 빠르다. 최선, 평균 = O(N log N) / 최악 = O(N^2)의 시간복잡도를 가진다. 1) 배열의 정 가운데 요소를 '피벗'으로 정한다. 2) 왼쪽부터 L 커서가 피벗 3보다 큰 값을 탐색, 오른쪽부터 R 커서가 피벗보다 작은 값을 탐색한다. 3) 발견한 값 5와 2를 교환한다. 4) 다시 피벗 3보다 큰 값, 작은 값을 각각 탐색한다. 4와 3을 교환한다. 5) R과 L이 교차했으므로 loop를 종료한다. 이때 L 기준으로 파티션을 나눈다. 왼쪽은 L 보다 작은 값들이 있고, 오른쪽은 큰 값들이 있다. 각 파티션의 요소가 한 개가 될 때까지 퀵정렬을 진행하면 모두 정렬이 되어있다. 1 2 3 4 5 6 7 8 9 10 11 1..

삽입 정렬의 장점은 살리고 단점을 보완하여 만든 정렬 알고리즘이다. 삽입정렬 장단점 장점 : 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다. 단점 : 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다. 셸 정렬은 정렬할 배열을 subfile로 쪼개서 각 subfile에서 삽입 정렬을 수행한 뒤 마지막에 모두 합쳐서 삽입정렬을 진행한다. (subfile=그룹?) 최선의 경우 O(N), 평균적으로 O(N^1.5), 최악의 경우 O(N^2)의 시간복잡도를 가진다. 각 subfile을 구성할 때는 배열의 k번째 요소를 추출하여 만드는데 이 k를 gap이라고 한다. 단계별로 gap을 줄여 subfile의 요소 개수가 증가시키고 gap이 1이 될 때 까지 반복한다. gap은 보통 배열 전체 길이의 절반에..

삽입 정렬은 선택한 요소를 자신보다 더 앞쪽 정렬된 부분의 알맞은 위치에 삽입하며 정렬해 나간다. 최선의 경우 O(n) / 평균, 최악 O(n^2)의 시간복잡도를 가진다. 1) 정렬이 되지 않은 부분의 가장 첫 번째 요소 selection[i]를 선택하고 2) 앞쪽 정렬된 부분의 알맞은 위치에 삽입한다. 2-1) 정렬된 부분을 한 칸씩 뒤로 밀어내며 이동하고 2-2) selection[i]보다 작은 요소를 만날 때까지 2-3) 혹은 가장 앞에 도달할 때까지 이동하여 삽입한다. 1 2 3 4 5 6 7 8 9 10 11 12 void insertionSort(int[] arr){ for(int i = 1 ; i = 0) && (arr[j] > temp)) { arr[j+1] = arr[j--]; } arr..

선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다. 최선, 평균, 최악 모두 O(N^2)의 시간복잡도를 가진다. 1. 아직 정렬되지 않은 부분에서 가장 작은 요소 selection[i]를 선택 2. selection[i]와 아직 정렬되지 않은 부분의 첫번째 요소를 교환 3. n-1회 반복 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void selectionSort(int[] list) { int indexMin, temp; for (int i = 0; i