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

Presentation on theme: "쉽게 배우는 알고리즘 3장. 정렬Sorting http://academy.hanb.co.kr."— Presentation transcript:

1 쉽게 배우는 알고리즘 3장. 정렬Sorting

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

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

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

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

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

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

8 ②에서 가장 큰 수를 찾기 위한 비교횟수: 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)

9 정렬할 배열이 주어짐 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

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

11 (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)

12 … 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

13 왼쪽부터 시작해 이웃한 쌍들을 비교해간다 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

14 앞의 작업을 반복하면서 계속 제외해 나간다 … 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

15 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)

16 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)

17 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 r]을 합하여         정렬된 하나의 배열 A[p ... r]을 만든다.

18 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++];

19 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

20 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

21 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

22 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

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

24 Animation (Merge Sort)
 2 7 7 2 | 9 4 4 9 7 7 | 2 2 9 9 | 4 4 7 2 9 4 수행시간: O(nlogn)

25 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[]

26 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

27 Animation (Quick Sort)
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)

28 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)

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

30 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

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

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

33 3 6 4 8 7 9 Heap 아님

34 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) 시간 소요!

35 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);

36 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

37 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

38 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

39 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

40 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

41 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

42 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

43 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

44 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

45 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

46 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

47 효율성(수행시간) 비교 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

48 효율성(수행시간) 실험 비교 - 정수 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

49 Thank you