쉽게 배우는 알고리즘 3장. 정렬Sorting http://academy.hanb.co.kr

3장. 정렬Sorting 은유, 그것은 정신적 상호연관성의 피륙을 짜는 방법이다. 은유는 살아있다는 것의 바탕이다. -그레고리 베이트슨

학습목표 기본 정렬 알고리즘을 이해한다. 정렬을 귀납적 관점에서 볼 수 있도록 한다. 1장과 2장에서 배운 기법을 사용해 각 정렬의 수행시간을 분석할 수 있도록 한다. 비교정렬의 한계를 이해하고, 선형시간 정렬이 가능한 조건과 선형시간 정렬 알고리즘을 이해한다.

Sorting Algorithms 대부분 O(n2)과 O(nlogn) 사이 Input이 특수한 성질을 만족하는 경우에는 O(n) sorting도 가능 E.g., input이 –O(n)과 O(n) 사이의 정수

원시적 Sorting 알고리즘들의 재조명 알고리즘을 보는 시각 원시적 정렬 알고리즘들을 관계 중심의 시각으로 다시 한 번 조명 flow 중심 관계 중심 원시적 정렬 알고리즘들을 관계 중심의 시각으로 다시 한 번 조명 생각하는 방법에 대한 좋은 연습 자료

Selection Sort 각 루프마다 하나의 원소만 남을 때까지 위의 루프를 반복 최대 원소를 찾는다 최대 원소와 맨 오른쪽 원소를 교환한다 맨 오른쪽 원소를 제외한다 하나의 원소만 남을 때까지 위의 루프를 반복

Finding the Recursive Structure The largest item 수행시간: (n-1)+(n-2)+···+2+1 = O(n2) Worst case Average case

②에서 가장 큰 수를 찾기 위한 비교횟수: n-1, n-2, …, 2, 1 ③의 교환은 상수 시간 작업 selectionSort(A[], n)       // A[1 ... n]을 정렬 {         for last ← n downto 2 {            // -------------- ①                 k ← theLargest(A, last); // A[1 ... last] 중 가장 큰 수 A[k] 찾기 ------ ②                 A[k] ↔ A[last];   // A[k]와 A[last]의 값을 교환 -------------- ③         } } theLargest(A[], last) // A[1 … last]에서 가장 큰 수의 인덱스를 리턴 largest ← 1; for i ← 2 to last if(A[i] > A[largest]) then largest ← i; return largest; 수행 시간: ①의 for 루프는 n-1번 반복 ②에서 가장 큰 수를 찾기 위한 비교횟수: n-1, n-2, …, 2, 1 ③의 교환은 상수 시간 작업 (n-1)+(n-2)+···+2+1 = n(n-1)/2 = O(n2)

정렬할 배열이 주어짐 Selection Sort의 작동 예 8 31 48 73 3 65 20 29 11 15 가장 큰 수를 찾는다 (73) 8 31 48 73 3 65 20 29 11 15 73을 맨 오른쪽 수(15)와 자리 바꾼다 1 의 첫번째 loop 8 31 48 15 3 65 20 29 11 73 맨 오른쪽 수를 제외한 나머지에서 가장 큰 수를 찾는다 (65) 8 31 48 15 3 65 20 29 11 73 65를 맨 오른쪽 수(11)와 자리 바꾼다 1 의 두번째 loop 8 31 48 15 3 11 20 29 65 73 맨 오른쪽 두 수를 제외한 나머지에서 가장 큰 수를 찾는다 (48) 8 31 48 15 3 11 20 29 65 73 . . . 8을 맨 오른쪽 수(3)와 자리 바꾼다 8 3 11 15 20 29 31 48 65 73 최종 배열 3 8 11 15 20 29 31 48 65 73

Bubble Sort Worst case Average case 수행시간: (n-1)+(n-2)+···+2+1 = n(n-1)/2 = O(n2)

(n-1)+(n-2)+···+2+1 = n(n-1)/2 = O(n2) bubbleSort(A[], n) // A[1 ... n]을 정렬 {         for last ← n downto 2             // ----------------- ①                 for i ← 1 to last-1        // ------------------ ②                         if (A[i] > A[i+1]) then A[i] ↔ A[i+1]; // 원소 교환 ----- ③ } 수행 시간: ①의 for 루프는 n-1번 반복 ②의 for 루프는 각각 n-1, n-2, …, 2, 1번 반복 ③은 상수 시간 작업 (n-1)+(n-2)+···+2+1 = n(n-1)/2 = O(n2)

… Bubble Sort의 작동 예 정렬할 배열이 주어짐 3 31 48 73 8 11 20 29 65 15 왼쪽부터 시작해 이웃한 쌍들을 비교해간다 3 31 48 73 8 11 20 29 65 15 순서대로 되어 있지 않으면 자리 바꾼다 3 31 48 8 73 11 20 29 65 15 3 31 48 8 11 73 20 29 65 15 3 31 48 8 11 20 73 29 65 15 … 3 31 48 8 11 20 29 65 15 73 맨 오른쪽 수(73)를 대상에서 제외한다 3 31 48 8 11 20 29 65 15 73

왼쪽부터 시작해 이웃한 쌍들을 비교해간다 3 31 48 8 11 20 29 65 15 73 순서대로 되어 있지 않은 경우에는 자리 바꾼다 3 31 8 48 11 20 29 65 15 73 3 31 8 11 48 20 29 65 15 73 3 31 8 11 20 48 29 65 15 73 3 31 8 11 20 29 48 65 15 73 3 31 8 11 20 29 48 65 15 73 3 31 8 11 20 29 48 15 65 73 맨 오른쪽 수(65)를 대상에서 제외한다 3 31 8 11 20 29 48 15 65 73

앞의 작업을 반복하면서 계속 제외해 나간다 … 3 8 73 65 48 31 29 20 15 11 두개짜리 배열의 처리를 끝으로 정렬이 완료된다 3 8 11 15 20 29 31 48 65 73 3 8 11 15 20 29 31 48 65 73

Insertion Sort 수행시간: O(n2) Worst case: 1+2+···+(n-2)+(n-1) = n(n-1)/2 Average case: ½ (1+2+···+(n-2)+(n-1)) 수행시간: O(n2)

insertionSort(A[], n)       // A[1 ... n]을 정렬 {         for i ← 2 to n  {                            ----------- ① loc ← i-1; newItem ← A[i]; // 이 지점에서 A[1…i-1]은 이미 정렬되어 있는 상태 while (loc ≥ 1 and newItem < A[loc]) { A[loc+1]  ← A[loc]; ② loc--; }                 A[loc+1] ← newItem;  }         수행시간: ①의 for 루프는 n-1번 반복 ②의 삽입은 최악의 경우 i-1회 비교 Worst case : 1+2+···+(n-2)+(n-1) = O(n2) Average case : ½ (1+2+···+(n-2)+(n-1)) = O(n2)

Merge Sort mergeSort(A[ ], p, r) // A[p ... r]을 정렬 {         if (p < r) then {                 q ← (p+q)/2;   -----------------------  ①   // p, q의 중간 지점 계산                 mergeSort(A, p, q);  ----------------  ②   // 전반부 정렬                 mergeSort(A, q+1, r); --------------  ③   // 후반부 정렬                 merge(A, p, q, r);  ------------------  ④   // 병합         } } merge(A[ ], p, q, r)         정렬되어 있는 두 배열 A[p ... q]와 A[q+1 ... r]을 합하여         정렬된 하나의 배열 A[p ... r]을 만든다.

Merge Sort (Continued…) merge(A[ ], p, q, r) // A[p … q]와 A[q+1 … r]을 병합하여 A[p … r]로 정렬된 상태로 만든다. // A[p … q]와 A[q+1 … r]는 이미 정렬되어 있음. {         i ← p; j ← q+1; t ← 1; while (i ≤ q and j ≤ r) { if(A[i] ≤ A[j]) then tmp[t++] ← A[i++]; // tmp[t] ← A[i]; t++; i++; else tmp[t++] ← A[j++]; // tmp[t] ← A[j]; t++; j++; } while (i ≤ q) // 왼쪽 부분 배열이 남은 경우 tmp[t++] ← A[i++]; while (j ≤ r) // 오른쪽 부분 배열이 남은 경우 tmp[t++] ← A[j++]; i ← p; t ← 1; while (i ≤ r) // 결과를 A[p … r]에 저장 A[i++] ← tmp[t++];

Merge Sort의 작동 예 1 2 3 4 정렬할 배열이 주어짐 31 3 65 73 8 11 20 29 48 15 배열을 반반으로 나눈다 31 3 65 73 8 11 20 29 48 15 1 각각 독립적으로 정렬한다 3 8 31 65 73 11 15 20 29 48 2 3 병합한다 (정렬완료) 3 8 11 15 20 29 31 48 65 73 4

p q r Merge Sort의 작동 예 3 8 31 65 73 11 15 20 29 48 i j t 8 31 65 73 11 15 20 29 48 i j 3 t 31 65 73 11 15 20 29 48 i j 3 8 t

31 65 73 15 20 29 48 i j 3 8 11 t 31 65 73 20 29 48 i j 3 8 11 15 t 31 65 73 29 48 i j 3 8 11 15 20 t

31 65 73 48 i j 3 8 11 15 20 29 t 65 73 48 i j 3 8 11 15 20 29 31 t 65 73 i j 3 8 11 15 20 29 31 48 t

i j 3 8 11 15 20 29 31 48 65 73 t

Animation (Merge Sort) 1 2 3 4 6 7 8 9 7 2 9 4  3 8 6 1 2 4 7 9 1 3 6 8 2 7 7 2 | 9 4 2 4 7 9 4 9 7 2 7 7 | 2 2 9 9 | 4 4 9 4 7 2 9 4 수행시간: O(nlogn)

Quick Sort – Divide and Conquer  quickSort(A[], p, r) // A[p ... r]을 정렬 {         if (p < r) then { q = partition(A, p, r);  // 분할 (Divide) quickSort(A, p, q-1);   // 왼쪽 부분배열 정렬 quickSort(A, q+1, r);   // 오른쪽 부분배열 정렬         } } partition(A[], p, r)         배열 A[p ... r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고         A[r]이 자리한 위치를 return 한다; [Pivot element] q ≤ x ≥ x x p r A[]

Quick Sort (Continued…)  partition(A[], p, r) { x ← A[r]; // 기준 원소 i ← p-1; // i 는 1구역의 끝 지점 for j ← p to r-1 // j 는 3구역의 시작 지점 if (A[j] ≤ x) then A[++i] ↔ A[j]; // i 값 증가 후 A[i] ↔ A[j] 교환 A[i+1] ↔ A[r]; // 기준 원소와 2구역 첫 원소 교환 return i+1; } 1 구역( ) : 기준 원소 x 보다 작거나 같은 원소들 2 구역( ) : 기준 원소 x 보다 큰 원소들 3 구역( ) : 아직 정해지지 않은 원소들 4 구역( ) : 기준 원소 x 자신 p r A[] 8 31 48 73 11 3 20 29 65 15 i j x

Animation (Quick Sort) 1 2 3 4 5 9 6 8 1 2 3 4 5 6 8 9 5 1 9 4 2 6 8 3 3 1 4 2 5 9 6 8 6 8 9 9 6 8 8 6 9 6 8 9 1 2 3 4 1 2 3 4 2 1 3 4 3 1 4 2 1 2 2 1 1 2 1 2 4 4 6 8 6 8 6 8 8 6 1 1 6 6 평균 수행시간: O(nlogn) 최악의 경우 수행시간: n(n-1)/2 = O(n2)

Quick Sort의 작동 예 (a) (b) 정렬할 배열이 주어짐. 첫 번째 수(15)를 기준 원소로 삼는다. 31 8 48 73 11 3 20 29 65 15 기준 원소(15)보다 작은 수는 기준 원소(15)의 왼쪽에, 나머지는 기준 원소(15)의 오른쪽에 오도록 재배치한다 8 11 3 15 31 48 20 29 65 73 (a) 기준 원소(15)의 왼쪽과 오른쪽을 각각 독립적으로 정렬한다 (정렬완료) 3 8 11 15 20 29 31 48 65 73 (b)

Partition의 예 p r (a) (b) (c) 31 8 48 73 11 3 20 29 65 15 i j 31 8 48

8 11 3 73 31 48 20 29 65 15 i j 8 11 3 73 31 48 20 29 65 15 i j 8 11 3 73 31 48 20 29 65 15 i j 8 11 3 73 31 48 20 29 65 15 (d) i 8 11 3 15 31 48 20 29 65 73 (e) i

Heap Sort – Complete binary tree 의미 : 프로그램이 실행될 때까지는 알 수 없는 가변적인 양 만큼의 데이터를 저장하기 위해, 프로그램의 프로세스가 사용할 수 있도록 미리 예약되어 있는 메인 메모리의 영역 Complete binary tree로서 다음의 성질을 만족 각 Node의 값은 자신의 children의 값보다 크지 않다 Heap Sort 주어진 배열을 Heap으로 만든 다음, 차례로 하나씩 Heap에서 제거함으로써 정렬

Heap 3 3 6 4 8 4 8 9 7 6 9 7 Heap Heap 아님

3 6 4 8 7 9 Heap 아님

Heap Sort (Continued…) heapSort(A[ ], n) // A[1 … n]을 정렬 { buildHeap(A, n); // Heap 만들기 for i ← n downto 2 { A[1] ↔ A[i]; // 원소 교환 heapify(A, 1, i-1); } 최악의 경우에도 O(n log n) 시간 소요!

Heap Sort (Continued…) buildHeap(A[ ], n) // A[1 … n]을 Heap으로 만들기 { for i ← └n/2┘downto 1 // └n/2┘은 Leaf이 아닌 Node들 중 맨 마지막 // Node의 Index 즉, Parent Node heapify(A, i, n); } Heapify(A[], k, n) left ← 2k; right ← 2k+1; // smaller : A[2k]와 A[2k+1] 중에 작은 원소 if (right ≤ n) then { // k가 두 자식을 가지는 경우 if (A[left] < A[right]) then smaller ← left; else smaller ← right; } else if (left ≤ n) then smaller ← left; // k의 왼쪽 자식만 있는 경우 else return; // A[k]가 Leaf Node / 끝 // 재귀적 조정 if (A[smaller] < A[k]) then { A[k] ↔ A[smaller]; heapify(A, smaller, n);

Heap은 Array를 이용해서 표현할 수 있다 1 3 2 3 6 4 1 2 3 4 5 6 A 3 6 4 8 9 7 4 5 6 8 9 7

Heap Sort의 작동 예 A A (b) (a) 7 3 6 4 6 4 8 9 3 8 9 7 Root (3) 제거 Root(3)와 마지막 Leaf(7) Swap 최소 Heap 구성 7 1 2 3 4 5 6 1 2 3 4 5 6 A A 3 6 4 8 9 7 7 6 4 8 9 3 3

Heap Sort의 작동 예 (계속) A A A (c) 4 (b) 7 6 7 6 4 9 3 8 8 9 3 Heap이 아니므로 Heapify 실행 Root(7)가 두 자식을 가지므로 Left(6)과 Right(4)를 비교 더 작은 Node(Smaller, 4)를 Root(7)와 Swap 8 9 3 8 9 3 Heap이 아님 1 2 3 4 5 6 A 4 6 7 8 9 3 1 2 3 4 5 6 A 7 6 4 8 9 3 4 1 2 3 4 5 6 A 7 6 4 8 9 3 7

Heap Sort의 작동 예(계속) A A A (c) (d) 4 9 6 7 6 7 8 9 3 8 4 3 Root (4) 제거 Root(4)와 마지막 Leaf(9) Swap 1 2 3 4 5 6 A 4 6 7 8 9 3 9 1 2 3 4 5 6 1 2 3 4 5 6 A A 4 6 7 8 9 3 9 6 7 8 4 3 4

Heap Sort의 작동 예(계속) A A A (e) 6 (d) 9 9 7 6 7 8 4 3 8 4 3 Heap이 아니므로 Heapify 실행 Root(9)가 두 자식을 가지므로 Left(6)과 Right(7)를 비교 더 작은 Node(Smaller, 6)를 Root(9)와 Swap 8 4 3 8 4 3 Heap이 아님 1 2 3 4 5 6 1 2 3 4 5 6 A A 6 9 7 8 4 3 9 6 7 8 4 3 6 1 2 3 4 5 6 A 9 6 7 8 4 3 9

Heap Sort의 작동 예(계속) A A A (e) 6 (f) 6 9 7 8 7 8 4 3 9 4 3 Heap이 아니므로 Heapify 실행 Root(9)가 왼쪽 자식만을 가지므로 Root(9)를 더 작은 Node(Smaller, 8)와 Swap 8 4 3 9 4 3 Heap이 아님 1 2 3 4 5 6 A 6 8 7 9 4 3 1 2 3 4 5 6 A 6 9 7 8 4 3 8 1 2 3 4 5 6 A 6 9 7 8 4 3 9

Heap Sort의 작동 예(계속) A A A 9 (f) 6 (g) 7 8 7 8 9 4 3 6 4 3 Root (6) 제거 Root(6)와 마지막 Leaf(9) Swap 1 2 3 4 5 6 A 6 8 7 9 4 3 1 2 3 4 5 6 9 A 9 8 7 6 4 3 1 2 3 4 5 6 A 6 8 7 9 4 3 6

Heap Sort의 작동 예(계속) A A A 9 (h) 7 (g) 8 7 8 9 6 4 3 6 4 3 Heap이 아니므로 Heapify 실행 Root(9)가 두 자식을 가지므로 Left(8)과 Right(7)를 비교 더 작은 Node(Smaller, 7)를 Root(9)와 Swap 6 4 3 6 4 3 Heap이 아님 1 2 3 4 5 6 1 2 3 4 5 6 A A 9 8 7 6 4 3 7 8 9 6 4 3 7 1 2 3 4 5 6 A 9 8 7 6 4 3 9

Heap Sort의 작동 예(계속) A A A 9 (h) 7 (i) 8 7 8 9 6 4 3 6 4 3 Root (7) 제거 Root(7)와 마지막 Leaf(9) Swap 1 2 3 4 5 6 A 1 2 3 4 5 6 7 8 9 6 4 3 9 A 9 8 7 6 4 3 1 2 3 4 5 6 A 7 8 9 6 4 3 7

Heap Sort의 작동 예(계속) A A A 9 (j) (i) 8 8 7 9 7 6 4 3 6 4 3 Heap이 아니므로 Heapify 실행 Root(9)가 왼쪽 자식만을 가지므로 Root(9)를 더 작은 Node(Smaller, 8)와 Swap 6 4 3 6 4 3 Heap이 아님 1 2 3 4 5 6 1 2 3 4 5 6 A 8 9 7 6 4 3 A 9 8 7 6 4 3 8 1 2 3 4 5 6 A 9 8 7 6 4 3 9

Heap Sort의 작동 예(계속) A A A 9 (k) (j) 8 8 7 9 7 6 4 3 6 4 3 Root (8) 제거 Root(8)와 마지막 Leaf(9) Swap Heap 1 2 3 4 5 6 1 2 3 4 5 6 A A 9 8 7 6 4 3 8 9 7 6 4 3 9 1 2 3 4 5 6 A 8 9 7 6 4 3 8

효율성(수행시간) 비교 Algorithms Best Case Average Case Worst Case Bubble Sort O(n2) Selection Sort Insertion Sort O(n) Heap Sort O(nlog2n) Merge Sort Quick Sort ~10/8/2003 ~10/24/2005

효율성(수행시간) 실험 비교 - 정수 60,000개 - Algorithm Time (sec) Bubble Sort 22.894 Selection Sort 10.842 Insertion Sort 7.438 Heap Sort 0.034 Merge Sort 0.026 Quick Sort 0.014 ~10/8/2003 ~10/24/2005

Thank you