4장. 정렬Sorting

4장. 정렬Sorting

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

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

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

기초적인 정렬 알고리즘 평균적으로 Θ(n2)의 시간이 소요되는 정렬 알고리즘들 선택정렬 버블정렬 삽입정렬

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

재귀적 구조 찾기 최대 원소 Worst case Average case 수행 시간: (n-1)+(n-2)+···+2+1 = Θ(n2) Worst case Average case

(n-1)+(n-2)+···+2+1 = Θ(n2) selectionSort(A[], n)      ▷ 배열 A[1 ... n]을 정렬한다 {         for last ← n downto 2 {                       ------------------ ①                 A[1 ... last] 중 가장 큰 수 A[k]를 찾는다;    ----------- ②                 A[k] ↔ A[last];  ▷ A[k]와 A[last]의 값을 교환 -------- ③         } } 수행 시간: ①의 for 루프는 n-1번 반복 ②에서 가장 큰 수를 찾기 위한 비교횟수: n-1, n-2, …, 2, 1 ③의 교환은 상수 시간 작업 (n-1)+(n-2)+···+2+1 = Θ(n2)

선택정렬의 작동 예 정렬할 배열이 주어짐 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

selectionSort(A[], n) {         for last ← n downto 2 {                 k ← theLargest(A, last);                 A[k] ↔ A[last];         } } theLargest(A[], last) largest ← 1;      for i ← 2 to last              if (A[i] > A[largest]) then largest ← i; return largest;

버블정렬 Worst case Average case 수행 시간: (n-1)+(n-2)+···+2+1 = Θ(n2)

(n-1)+(n-2)+···+2+1 = Θ(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 = Θ(n2)

버블정렬의 작동 예 정렬할 배열이 주어진다 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 6555 7333

… 버블정렬의 작동 예 앞의 작업을 반복하면서 계속 제외해 나간다 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

bubbleSort(A[], n)   { for last ← n downto 2{ sorted ← true; for i ← 1 to last-1 { if (A[i] > A[i+1]) then { A[i] ↔ A[i+1]; sorted ← false; } if (sorted = true) then return;

삽입정렬 수행 시간: Θ(n2) Best case: Θ(n) 10 집어넣기 29 shift 10 삽입 14 집어넣기 14 삽입 37 집어넣기 37 삽입(자신의 자리에 그대로) 13 집어넣기 37, 29, 14 shift 13 삽입 Worst case: 1+2+···+(n-2)+(n-1) Average case: ½ (1+2+···+(n-2)+(n-1)) 수행 시간: Θ(n2) Best case: Θ(n)

Worst case: 1+2+···+(n-2)+(n-1) = Θ(n2) insertionSort(A[], n)       ▷ A[1 ... n]을 정렬한다 {         for i ← 2 to n                               ---------------------- ①                  A[1 ... i]의 적당한 자리에 A[i]를 삽입한다;  ----------- ②         } 수행 시간: ①의 for 루프는 n-1번 반복 ②의 삽입은 최악의 경우 i-1회 비교 Worst case: 1+2+···+(n-2)+(n-1) = Θ(n2) Average case: ½ (1+2+···+(n-2)+(n-1)) = Θ(n2) Best case: 1+1+···+1+1 = Θ(n) n-1

insertionSort(A[], n)  { for i ← 2 to n { loc ← i – 1; newItem ← A[i]; while (loc ≥ 1 and newItem < A[loc]){ A[loc+1] ← A[loc]; loc = loc – 1; } A[loc+1] ← newItem;

삽입정렬의 귀납적 확신 배열 A[1]만 놓고 보면 배열 A[1 … k]까지 정렬되어 있다면 정렬되어 있음 고등학교에서 배운 수학적 귀납법과 다를 바 없음

고급 정렬 알고리즘 평균적으로 Θ(n log n)의 시간이 소요되는 정렬 알고리즘들 병합정렬 퀵정렬 힙정렬

병합정렬 merge(A[ ], p, q, r) mergeSort(A[ ], p, r) ▷ A[p ... r]을 정렬한다. {         if (p < r) then {                 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]을 만든다.

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

p q r 병합(merge)의 작동 예 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

병합(merge)의 작동 예 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

병합(merge)의 작동 예 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

병합(merge)의 작동 예 i j 3 8 11 15 20 29 31 48 65 73 t

Merge 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++]; else tmp[t++] ← A[j++]; } while(i ≤ q) tmp[t++] ← A[i++]; while(j ≤ r) tmp[t++] ← A[j++]; i ← p; t ← 1; while(i ≤ r) A[i++] ← tmp[t++];

Animation (병합정렬) 수행 시간: Θ(nlogn) 1 2 3 4 6 7 8 9 7 2 9 4  3 8 6 1 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 수행 시간: Θ(nlogn)

퀵정렬 { if (p < r) then { q = partition(A, p, r); ▷ 분할  quickSort(A[], p, r) ▷ A[p ... r]을 정렬한다 {         if (p < r) then { q = partition(A, p, r);  ▷ 분할 quickSort(A, p, q-1);   ▷ 왼쪽 부분 배열 정렬 quickSort(A, q+1, r);   ▷ 오른쪽 부분 배열 정렬         } } partition(A[], p, r)         배열 A[p ... r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고         A[r]이 자리한 위치를 리턴한다; }  

Animation (퀵정렬) 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 평균 수행 시간: Θ(nlogn) 최악의 경우 수행 시간: Θ(n2)

퀵정렬의 작동 예 (a) (b) 정렬할 배열이 주어짐. 첫번째 수를 기준으로 삼는다. 31 8 48 73 11 3 20 29 65 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

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

Partition { x ← A[r]; i ← p – 1; for j ← p to r – 1  partition(A[], p, r) { x ← A[r]; i ← p – 1; for j ← p to r – 1 if(A[j] ≤ x) then A[++i] ↔ A[j]; A[i+1] ↔ A[r]; return i+1; }

힙정렬 힙Heap 힙정렬 Complete binary tree로서 다음의 성질을 만족한다 각 노드의 값은 자신의 children의 값보다 크지 않다 힙정렬 주어진 배열을 힙으로 만든 다음, 차례로 하나씩 힙에서 제거함으로써 정렬한다

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

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

힙 3 6 4 8 7 9 힙 아님

힙은 배열을 이용해서 표현할 수 있다 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

힙 만들기 (a) (b) (c) (e) (d) 7 9 4 8 6 3 7 9 3 8 6 4 7 6 3 8 9 4 A 7 9 4 1 5 2 7 9 3 8 6 4 힙 만들기 (a) (b) (c) 7 6 3 8 9 4 1 2 3 4 5 6 2 A 7 9 4 8 6 3 4 5 (e) (d) 1 3 6 4 8 9 7 3 6 7 8 9 4 3 3 6 1 2 3 4 5 6 A 3 6 4 8 9 7

정렬 (a) 3 (b) (c) 4 7 6 4 6 4 6 7 8 9 7 8 9 3 8 9 3 (f) 6 (e) (d) 6 9 8 3 제거 7 6 4 6 4 6 7 8 9 7 8 9 3 8 9 3 4 제거 (f) 6 (e) (d) 6 9 8 7 9 7 6 7 9 4 3 8 4 3 8 4 3

6 제거 (h) 7 제거 9 9 7 (i) (g) 8 7 8 9 8 7 6 4 3 6 4 3 6 4 3 (j) (k) 8 제거 8 9 8 7 9 7 6 4 3 6 4 3

if(A[left] < A[right]) then smaller ← left; else smaller ← right; buildHeap(A[ ], n) { for i ← n/2 downto 1 heapify(A, i, n) } heapify(A[ ], k, n) left ← 2k; right ← 2k+1; if(right ≤ n) then{ if(A[left] < A[right]) then smaller ← left; else smaller ← right; else if (left ≤ n) then smaller ← left; else return; if(A[smaller] < A[k]) then{ A[k] ↔ A[smaller]; heapify(A, smaller, n); ~9/17/2007

Θ(n) 정렬 두 원소를 비교하는 것을 기본 연산으로 하는 정렬의 하한선은 Ω (n log n)이다 계수정렬Counting Sort 원소들의 크기가 모두 –O(n) ~ O(n) 범위에 있을 때 기수정렬Radix Sort 원소들이 모두 k 이하의 자릿수를 가졌을 때 (k: 상수)

기수정렬Radix Sort radixSort(A[ ], n, k) { for i ← 1 to k } ▷ 원소들이 각각 최대 k 자리수인 A[1…n]을 정렬한다 ▷ 가장 낮은 자리수를 1번째 자리수라 한다 { for i ← 1 to k i 번째 자리수에 대해 A[1…n] 을 안정을 유지하면서 정렬한다; } 안정성 정렬Stable sort 같은 값을 가진 원소들은 정렬 후에도 원래의 순서가 유지되는 성질을 가진 정렬을 일컫는다.

Running time: Θ(n) ← d: a constant 0123 2154 0222 0004 0283 1560 1061 2150 1560 2150 1061 0222 0123 0283 2154 0004 0004 0222 0123 2150 2154 1560 1061 0283 0004 1061 0123 2150 2154 0222 0283 1560 0004 0123 0222 0283 1061 1560 2150 2154 Running time: Θ(n) ← d: a constant

계수정렬Counting Sort for j ← n downto 1 { countingSort(A, B, n) { ▷ A[1…n]: 입력 배열 ▷ B[1…n]: 배열 A를 정렬한 결과 { for i = 1 to k C[i] ← 0; for j = 1 to n C[A[j]]++; ▷ 이 시점에서의 C[i] : 값이 i인 원소의 총 수 C[i] ← C[i] + C[i-1] ; ▷ 이 시점에서의 C[i] : i보다 작거나 같은 원소의 총 개수 for j ← n downto 1 { B[C[A[j]] ← A[j]; C[A[j]]--; }

효율성 비교 Worst Case Average Case Selection Sort n2 Bubble Sort Insertion Sort Mergesort nlogn Quicksort Counting Sort n Radix Sort Heapsort ~10/8/2003 ~10/24/2005

Thank you