10장 정렬

순서 10.1 선택 정렬 10.2 버블 정렬 10.3 삽입 정렬 10.4 합병 정렬 10.5 퀵 정렬 10.6 히프 정렬 10.7 쉘 정렬 10.8 기수 정렬 10.9 트리 정렬

10.1 선택 정렬 (1) 기본 개념 방법 SelectionSort 알고리즘 잘못된 위치에 들어가 있는 원소를 찾아 그것을 올바른 위치에 집어 넣는 원소 교환 방식으로 정렬 방법 가장 작은 원소를 찾아 첫 번째 위치의 원소와 교환 두 번째로 작은 원소를 찾아 두 번째 위치의 원소와 교환 나머지 a[i], ···, a[n-1] 원소 중 가장 작은 원소를 선택해서 a[i] 원소와 계속 교환 SelectionSort 알고리즘 전체 비교 연산 수 = n(n-1)/2, 시간 복잡도 = O(n2) SelectionSort(a[], n) for (i ← 0; i < n; i ← i + 1) do { a[i], ··· , a[n-1] 중에서 가장 작은 원소 a[k]를 선택; a[k]를 a[i]와 교환; }

10.1 선택 정렬 (2) SelectionSort의 실행 예 a [] : [0] [1] [2] [3] [4] 초기 : 5 2 8 3 1 for 루프 i = 0 : a [0]과 a [4] 교환 i = 1 : a [1]과 a [1] 교환 i = 2 : a [2]와 a [3] 교환 i = 3 : a [3]과 a [4] 교환 파란색 : 서로 교환된 원소

10.1 선택 정렬 (3) SelectionSort의 C 구현 void selectionSort(int a[], int size) {   int i, j;   int min, temp;   for (i = 0; i < size-1; i++) {     min = i; /* a[j] … a[size-1] 사이에 가장 작은 원소의 인덱스(min)를 찾음 */     for (j = i+1; j < size; j++) {       if (a[j] < a[min])         min = j;     } /* a[i]와 a[j] … a[size-1] 사이의 가장 작은 원소 int_array[min]를 교환 */        temp = a[i];     a[i] = a[min];     a[min] = temp;   } }

10.1 선택 정렬 (4) SelectionSort의 Main 함수 (샘플 프로그램) int main() { int i;   int a[5]={5, 2, 8, 3, 1};   printf("정렬전 배열 원소\n");   for (i = 0; i < 5; i++)    printf("%2d", a[i]);   selectionSort(a, 5);   printf("정렬된 배열 원소\n"); } <실행결과> 정렬전 배열 원소 : 5 2 8 3 1 정렬된 배열 원소 : 1 2 3 5 8

10.2 버블 정렬 (1) 기본 개념 배열을 검사하여 두 인접한 원소가 오름차순 정렬 순서에 맞지 않으면 이들을 서로 교환 방법 a[0]과 a[1]을 비교하여 정렬순서에 맞도록 교환 a[1]과 a[2]을 비교하여 정렬순서에 맞도록 교환 a[n-2]와 a[n-1]을 비교하여 정렬순서에 맞도록 교환 제일 큰 원소가 배열의 n-1 위치로 이동 (→패스 1) 배열 처음부터 다시 비교 및 정렬 … 마지막 패스로 a[0]과 a[1]을 비교하여 정렬 (→패스 n-1)

10.2 버블 정렬 (2) BubbleSort 알고리즘 의사코드 전체 비교 연산 수 = n(n-1)/2, 시간 복잡도 = O(n2) BubbleSort(a[], n) for (i ← n - 1; i ≥ 0; i ← i - 1) do { for (j ← 0; j < i; j ← j+1) do { if (a[j] > a[j+1]) then a[j]와 a[j+1]을 교환; }

10.2 버블 정렬 (3) BubbleSort의 실행 예 a [] : [0] [1] [2] [3] [4] 패스 1 : 초기 : 5 2 8 3 1 a [4] 확정 패스 2 : a [3] 확정 패스 3 : a [2] 확정 패스 4 : a [1] 확정, a [0] 자동 확정 파란색 : 서로 교환되는 원소

10.2 버블 정렬 (4) BubbleSort의 C 구현 void bubbleSort(int a[], int size) {    int i, j, temp;   for (i = size - 1; i >= 0; i--) { for (j = 0; j <= i; j++)   { if (a[j-1] > a[j])      {                   temp = a[j-1];                   a[j-1] = a[j];                   a[j] = temp;                 }            }             }   }

10.3 삽입 정렬 (1) 기본 개념 가정사항 S : 정렬되어 있는 배열의 왼쪽 부분 U : 정렬되어 있지 않은 배열의 오른쪽 부분 정렬되어 있지 않은 U의 왼쪽 끝에서 삽입할 원소를 찾아 정렬되어 있는 S의 적절한 위치에 삽입 방법 U의 왼쪽에서 삽입할 원소 k를 선택 k를 삭제 (빈자리) S에 있는 k보다 큰 원소들을 오른쪽으로 이동 k를 S에 만들어진 빈자리에 삽입 U의 모든 원소들이 S에 삽입될 때까지 반복 시간 복잡도 = O(n2)

(b) k[i]를 제거하여 빈자리를 만듦(k ← k[i]) 10.3 삽입 정렬 (2) InsertionSort에서 원소 k(=a[i])의 삽입과정(1) 삽입할 원소 k S = 정렬된 원소 U = 정렬 안된 원소 a[] : [0] [i-1] [i] [n-1] (a) 초기 단계 S U 삽입할 원소 k 빈자리 a[] : [0] [i-1] [i] [n-1] (b) k[i]를 제거하여 빈자리를 만듦(k ← k[i])

(c) K보다 큰 원소는 오른편으로 한 자리씩 이동 10.3 삽입 정렬 (3) InsertionSort에서 원소 k(=a[i])의 삽입과정(2) → 이동 S U k 빈자리 a[] : [0] [n-1] (c) K보다 큰 원소는 오른편으로 한 자리씩 이동 S U 삽입된 k a[] : [0] [i] [n-1] (d) K를 빈자리에 삽입

10.3 삽입 정렬 (4) InsertionSort 알고리즘 insertionSort(a[], n) // 원소 temp는 a[i], 0 < i < n, // 원소 temp(=a[i], 0 < i < n)를 부분 배열 a[0 : i-1]에 오름차순으로 삽입 for (i = 1; i < n; i ← i + 1) { // 두 번째 원소 a[1]부터 temp ← a[i]; //temp는 임시 저장소 j ← i; if (a[j-1] > temp) then move ← true else move ← false; while (move) do { a[j] ← a[j-1]; // a[j-1]을 오른쪽으로 한자리 이동시켜 빈자리를 만듦 j ← j-1; if (j > 0 and a[j-1] > temp) then move ← true } a[j] ← temp; //temp를 빈자리에 삽입 } // for end insertionSort()

10.3 삽입 정렬 (5) InsertionSort 실행 예 배열 a = [3, 1, 9, 8, 4] [0] [1] [2] [3] [4] a [] : 3 1 9 8 4 i = 1 : temp = 1 [ 3 ] [ 1 3 ] i = 2 : temp = 9 9 ] i = 3 : temp = 8 9 ] i = 4 : temp = 4 [ ] : 정렬된 원소의 배열

10.4 합병 정렬 (1) 기본 개념 방법 MergeSort 알고리즘 배열을 이등분하여 각각을 정렬한 후 합병 배열 A를 L과 R로 이등분한 후 배열 L과 R을 각각 정렬 정렬된 배열 L과 R에서 작은 원소를 삭제하여 새로운 임시 공백 배열 S에 차례대로 삽입 원래의 배열 a에 복사 시간 복잡도 : O(nlogn) MergeSort 알고리즘 mergeSort(a[], m, n) for (a[m : n]의 원소수 > 1) then { divide a[m : n] into a[m : middle] and a[middle+1 : n]; mergeSort(a[], m, middle); mergeSort(a[], middle+1, n); merge(a[m : middle], a[middle+1 : n]); } end mergeSort()

10.4 합병 정렬 (2) Merge 알고리즘의 수행 과정(1) a = [8, 1, 23, 15, 31, 2, 26, 12] L 1 8 15 23 R 2 12 26 31 S 0 : (초기) m q t L 1 8 15 23 R 2 12 26 31 S 1 1) m q t L 1 8 15 23 R 2 12 26 31 S 1 2 2) m q t L 1 8 15 23 R 2 12 26 31 S 1 2 8 3) m q t

10.4 합병 정렬 (3) Merge 알고리즘의 수행 과정(2) 4) m q t 5) m q t 6) m q t 7) m q L 1 8 15 23 R 2 12 26 31 S 1 2 8 12 4) m q t L 1 8 15 23 R 2 12 26 31 S 1 2 8 12 15 5) m q t L 1 8 15 23 R 2 12 26 31 S 1 2 8 12 15 23 6) m q t L 1 8 15 23 R 2 12 26 31 S 1 2 8 12 15 23 26 31 7) m q t 8) a 1 2 8 12 15 23 26 31 원래의 배열 a에 복사

10.4 합병 정렬 (4) mergeSort 프로그램(1) void internalMergeSort(int a[], int temp[], int left, int right) ; void merge(int a[], int temp[], int left, int middle, int right) ; void  mergeSort(int a[], int temp[], int size); /* 합병 절렬의 메인 함수*/ { internalMergeSort(int a[], temp, 0, size - 1); } /*순환 호출을 하는 MergeSort의 보조 함수 */ void internalMergeSort(int a[], int temp[], int left, int right) { int middle;   if (right > left) { /* 정렬할 원소가 2개 이상인 경우 */     middle = (right + left) / 2;    internalMergeSort (a, temp, left, middle);    internalMergeSort (a, temp, middle+1, right);    merge(a, temp, left, middle+1, right);   } }

10.4 합병 정렬 (5) mergeSort 프로그램(2) 단점 : 주어진 배열과 동일한 크기의 임시배열 temp[]가 필요 void merge(int a[], int temp[], int left, int middle, int right) { /* internalMergeSort의 보조 함수 */   int i, left_end, numElements, temp_pos;  left_end = middle - 1;   temp_pos = left;   num_elements = right - left + 1;  while ((left <= left_end) && (middle <= right)) {     if (a[left] <= a[middle])        temp[temp_pos++] = a[left++];     else       temp[temp_pos++] = a[middle++]; } while (left <= left_end) { /* 왼쪽 부분 배열에 원소가 남아 있는 경우 */ temp[temp_pos++] = a[left++]; while (middle <= right) { /* 오른쪽 부분 배열에 원소가 남아 있는 경우 */       temp[temp_pos++] = a[middle++];   for (i=0; i <= numElements; i++) { /* 배열 temp[]를 a[]로 복사 */      a[right] = temp[right];     right = right - 1;

10.4 합병 정렬 (6) MergeSort 알고리즘의 분해 과정 [m] [middle] [n] a[] : 4 6 7 1 3 8 4 6 7 1 3 7 4 3 8 4 6 7 1 3 7 4 4 3 8 4 6 7 1 3 7 4 4 3 8 7 1 4 3

10.4 합병 정렬 (7) MergeSort 알고리즘의 합병 과정 Temp[] : a[] : [m][m+1] [n] 7 1 4 3 4 6 1 7 3 7 4 3 4 8 4 6 1 3 7 4 7 3 4 8 1 3 4 6 7 3 4 7 8 Temp[] : 1 3 4 6 7 8 a[] : 1 3 4 6 7 8 [m][m+1] [n]

10.5 퀵 정렬 (1) 기본 개념 방법 분할 정복(divide and conquer) 정렬 방법의 하나 배열 a[m:n]의 한 원소를 pivot으로 선정 pivot 을 기준으로 두 개의 파티션으로 분할 왼쪽 파티션 : pivot보다 작은 값의 원소들로 구성 오른쪽 파티션 : pivot 보다 크거나 같은 값의 원소들로 구성 각각의 파티션에 대해 다시 퀵 정렬을 순환 적용 pivot 선정 및 파티션 분할 시간 복잡도 : O(nlogn) pivot [m] [n] a[] 3 1 4 5 9 7 8 ＜ pivot ≥ pivot

10.5 퀵 정렬 (2) QuickSort 알고리즘 기본 골격 if (a[m : n]의 원소 ≤ 1) then return; (a[]의 원소 하나를 pivot으로 선정하여 A[m : n]을 leftPartition과 rightPartition으로 분할); (quickSort(leftPartition)); (quickSort(rightPartition)); quickSort(a[], m, n) // 배열 a[]의 부분 배열 a[m : n]을 오름차순으로 정렬 if (m ≥ n) then return; // 정렬할 원소 수가 0이거나 1일 때는 복귀 p ← partition(a, m, n); // p는 파티션이 끝난 뒤에 사용된 pivot의 인덱스 quickSort(a[], m, p-1); quickSort(a[], p+1, n); end auickSort()

10.5 퀵 정렬 (3) partition 알고리즘 목적 단계별 분할 과정 부분 배열 a[i : j]의 중앙 원소를 pivot 값으로 정하고 왼쪽과 오른쪽 파티션으로 분할 단계별 분할 과정 a[i : j]의 중앙 인덱스 값 middle을 선정하여 a[middle]의 원소 x를 분할의 기준값, pivot으로 정한다. a[middle]의 원소 x와 a[]의 제일 왼쪽 끝에 있는 a[i]의 원소 y를 서로 교환 (pivot 인덱스 p는 i를 지시) pivot ← x a[] : y ? x [i] [middle] [j] p a[] : x ? y [i] [middle] [j]

10.5 퀵 정렬 (4) a[i+1 : j]의 모든 원소 a[k]를 검사하여 pivot 보다 작을 경우 : a[i+1 : p]에 삽입 (p를 1 확장) pivot 보다 크거나 같을 경우 : a[p+1 : j]에 삽입 항상 (a[i+1 : p] ＜ pivot, a[p+1 : k] ≥ pivot)을 유지 모든 원소의 검사 완료 후 pivot 인덱스가 확정되면 a[i]와 a[p]를 교환하여 pivot 값을 제자리에 저장 분할 완료시 확정된 pivot 인덱스 p를 반환 p k pivot = x a[] : x ? [i] ＜ pivot ≥ pivot [j] p k pivot = x a[] : x z [i] ＜ pivot ≥ pivot [j] pivot k a[] : z x [i] ＜ pivot [p] ≥ pivot [j]

10.5 퀵 정렬 (5) partition 알고리즘 partiton(a[], i, j) middle ← (i + j) / 2; // middle은 a[]의 중앙 인덱스 값 pivot ← a[middle]; // a[]의 중앙 원소값을 pivot으로 설정 a[middle] ← a[i]; // a[i]와 a[middle]을 서로 교환 a[i] ← pivot; // a[i]는 pivot 값을 보관 p ← i; // p는 두 파티션의 경계를 지시하는 인덱스 for (k ←i+1; k ≤ j; k ← k+1) do { // a[i]를 제외한 a[i+1 : j]에 있는 모든 원소 a[k]들을 검사하여 if (a[k] < pivot) then { // a[k]가 pivot보다 작으면 p ← p+1; // p를 1 증가시켜 a[k]를 p 인덱스 범위 temp ← a[p]; // 안으로 포함되게 함 a[p] ← a[k]; a[k] ← temp; } temp ← a[i]; // a[i]와 a[p]를 교환 a[i] ← a[p]; a[p] ← temp; return p; end partition()

10.5 퀵 정렬 (6) 퀵 정렬 수행 과정 (1) 배열 a = [ 3 1 4 5 9 8 7 ]에서 초기 배열 a[i : j], i = 0, j = 6 a : [0] [1] [2] [3] [4] [5] [6] [ 3 1 4 5 9 8 7 ] pivot을 중앙 원소값(a[3]) 5로 선정하고 a[i] 원소와 교환 [ 5 1 4 3 9 8 7 ] k를 1씩 증가, a[i+1 : p]에 있는 원소가 pivot보다 작게 교환 k가 j까지 증가되었을 때, p를 고정시키고 a[p]와 a[i] 원소 교환 pivot, a[p]를 중심으로 2개의 파티션이 생성 [ 3 1 4 ] 5* [ 9 8 7 ] p k k p _는 교환될 원소, *는 각 단계에서 확정된 pivot

10.5 퀵 정렬 (7) 퀵 정렬 수행 과정 (2) 배열 원소 수의 pivot이 결정될 때까지 정렬을 수행 파티션 i = 0, j = 2에 대해 순환적으로 퀵 정렬을 수행 a : [0] [1] [2] [3] [4] [5] [6] [ 3 1 4 ] 5 [ 9 8 7 ] p k [ 1 3 4 ] 5 [ 9 8 7 ] P를 확정시키고 공백 파티션과 파티션 i = 1, j = 2를 생성 1* [ 3 4 ] 5 [ 9 8 7 ] 파티션 i = 1, j = 2에 대해 다시 퀵 정렬을 수행 p k 1 [ 3 4 ] 5 [ 9 8 7 ] 1 3* [ 4 ] 5 [ 9 8 7 ] 1 3 4* 5 [ 9 8 7 ]

10.5 퀵 정렬 (8) 퀵 정렬 수행 과정 (3) 제자리 알고리즘(in-place algorithm) 파티션 i = 4, j = 6에 대해 순환적으로 퀵 정렬을 수행 a : [0] [1] [2] [3] [4] [5] [6] 1 3 4 5 [ 8 9 7 ] 1 3 4 5 [ 8 7 9 ] 1 3 4 5 [ 7 ] 8* [ 9 ] 1 3 4 5 7* 8 [ 9 ] 1 3 4 5 7 8 9* 제자리 알고리즘(in-place algorithm) 별도의 배열을 사용하지 않고 원래의 배열 위에서만 정렬을 수행

10.5 퀵 정렬 (9) QuickSort의 C 구현 int partition(int a[], int left, int right); void internalQuickSort(int a[], int left, int right); void quickSort(int a[], int size) { /* 퀵 정렬 함수 */    internalQuickSort(a, 0, size -1); } void internalQuickSort(int a[], int left, int right) {/* quickSort()의 보조 함수 */    int pivot;    if (left > right) then return;    pivot = partition(a, left, right);    internalQuickSort(a, left, pivot-1);    internalQuickSort(a, pivot+1, right); int partition(int a[], int left, int right) {/* internalQuickSort()의 보조 함수 */ …… /* partition 알고리즘의 C 코드 */   ……    return pivot;

10.6 히프 정렬 (1) 기본 개념 방법 최대 히프를 이용한 정렬 기법 정렬할 원소를 모두 공백 히프에 삽입 루트 노드(가장 큰 원소)를 삭제하여 리스트 뒤에 삽입 삽입된 원소를 제외한 나머지 원소들에 대해 반복 수행 시간 복잡도 : O(nlogn) for (i ← 0; i < n; i ← i+1) do { insertHeap(heap, a[i]); } for (i ← n-1; i ≥ 0, i ← i-1) do { a[i] ← deleteHeap(heap);

10.6 히프 정렬 (2) HeapSort 알고리즘 Heapify()를 호출하여 배열 a[1 : n]을 히프 구조로 변환 원소를 교환하여 최대 원소 저장 Heapify()를 호출하여 나머지 원소를 히프로 재구성 heapSort(a[]) n ← a.length-1; // n은 히프 크기(원소의 수) // a[0]은 사용하지 않고 a[1 : n]의 원소를 오름차순으로 정렬 for (i ← n/2; i ≥ 1; i ← i-1) do { // 배열 a[]를 히프로 변환 heapify(a, i, n); // i는 내부 노드 for (i ← n-1; i ≥ 1; i ← i-1) do { // 배열 a[]를 오름차순으로 정렬 temp ← a[1]; // a[1]은 제일 큰 원소 a[1] ← a[i+1]; // a[1]과 a[i+1]을 교환 a[i+1] ← temp; heapify(a, 1, i); } end heapSort()

10.6 히프 정렬 (3) Heapify 알고리즘 완전 2진 트리를 히프로 변환 heapify(a[], h, m) // 루트 h를 제외한 h의 왼쪽 서브트리와 오른쪽 서브트리는 히프 // 현재 시점으로 노드의 최대 레벨 순서 번호는 m for (j ← 2*h; j ≤ m; j ← 2*j) do { if (j < m) then if (a[j] < a[j+1]) then j ← j+1; // j는 값이 큰 왼쪽 또는 오른쪽 자식 노드 if (a[h] ≥ a[j]) then exit else a[j/2] ← a[j]; // a[j]를 부모 노드로 이동 } a[j/2] ← a[h]; end heapify()

10.6 히프 정렬 (4) HeapSort(a[], 10) 실행 예(1) 완전 2진 트리 표현 히프 구조 변환 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] - 20 40 50 70 30 100 80 10 90 60 a[] : 1 20 100 2 40 3 50 90 80 4 70 5 30 6 100 7 80 70 60 50 20 8 10 9 90 60 10 10 40 30

10.6 히프 정렬 (5) HeapSort(a[], 10) 실행 예(2) [1] [2] [3] [4] [5] [6] [7] 초기 : 히프(크기 10)로 변환 : (두번째 for 루프) i = 9 : (i = 히프 크기) i = 8 : i = 7 : i = 6 : i = 5 : i = 4 : i = 3 : i = 2 : i = 1 : [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 20 40 50 70 30 100 80 10 90 60 파란색 : 정렬 완료된 원소값

10.6 히프 정렬 (6) 히프 정렬 과정에서의 히프 변화(1) 100 90 80 20 50 60 70 10 40 30 (a) 히프 크기 = 10 90 70 80 20 50 60 40 10 30 100 (b) 히프 크기 = 9 80 70 50 20 30 60 40 10 90 100 (c) 히프 크기 = 8 70 60 50 20 30 10 40 80 90 100 (d) 히프 크기 = 7

10.6 히프 정렬 (7) 히프 정렬 과정에서의 히프 변화(2) 60 40 50 70 30 10 20 80 90 100 (e) 히프 크기 = 6 (f) 히프 크기 = 5 50 40 30 70 60 10 20 80 90 100 (g) 히프 크기 = 4 40 20 30 70 60 50 10 80 90 100 (h) 히프 크기 = 3 30 20 10 70 60 50 40 80 90 100

10.6 히프 정렬 (8) 히프 정렬 과정에서의 히프 변화(3) (i) 히프 크기 = 2 20 10 30 70 60 50 40 80 90 100 (j) 히프 크기 = 1 : 정렬 종료 10 20 30 70 60 50 40 80 90 100

10.6 히프 정렬 (9) HeapSort의 C 구현 void heapSort(int a[], int size) {      int i, temp;      for ( i = size /2; i >= 1; i-- )           heapify(a, i, size);           for ( i = size /2; i >= 1; i-- )  {            temp = a[1];            a[1] = a[i+1];            a[i+1] = temp;            heapify(a, 1, i);          } } void heapify(int a[], int h, int m) { /* HeapSort()의 보조 함수 */ ……       /* heapify 알고리즘의 C 코드 */

10.7 쉘 정렬 (1) 기본 개념 방법 원소의 비교 연산과 먼 거리의 이동을 줄이기 위해 몇 개의 서브리스트로 나누어 삽입 정렬을 반복 수행 방법 정렬에서 사용할 간격(interval) 결정 전체 원소 수 n의 1/3, 다시 이것의 1/3 ··· interval이 작아질수록 짧은 거리를 이동하고 원소 이동이 적음 첫 번째 interval에 따라 서브리스트로 분할 각 서브리스트에 대해 삽입 정렬 수행 두 번째 interval에 따라 서브리스트로 분할 리스트 전체에 대해 삽입 정렬 수행 (마지막 interval = 1) 시간 복잡도 : O(n1.25) 반복

(c) 정렬된 interval-5 서브리스트 10.7 쉘 정렬 (2) 쉘 정렬 예 (1) : interval = 5 i : a[i] : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 3 14 12 4 10 13 1 5 2 7 9 6 8 11 (a) 배열 : a[0 :13] i : a[i] : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 3 14 12 4 10 13 1 5 2 7 9 6 8 11 [3 9] [14 6] [12 8] [4 11] [10 7] (b) 5개의 interval-5 서브리스트 i : a[i] : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 3 1 5 2 7 9 6 8 4 10 13 14 12 11 (c) 정렬된 interval-5 서브리스트

(e) 정렬된 interval-3 서브리스트 10.7 쉘 정렬 (3) 쉘 정렬 예 (2) : interval = 3 쉘 정렬 예 (3) : interval = 1 i : a[i] : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 3 1 5 2 7 9 6 8 4 10 13 14 12 11 [3 12] [1 11] [5 14] (d) 3개의 interval-3 서브리스트 i : a[i] : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 2 1 4 3 7 5 6 8 9 10 11 14 12 13 (e) 정렬된 interval-3 서브리스트 i : a[i] : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (f) 최종 정렬 결과

10.7 쉘 정렬 (4) ShellSort 알고리즘 shellSort(a[], n) interval ← a.length; while (interval > 1) do { interval ← 1 + interval / 3; for (i ← 0; i < interval; i ← i+1) do { intervalSort(A, i, interval); } end shellSort()

10.7 쉘 정렬 (5) intervalSort 알고리즘 intervalSort(a[], i, interval, n) // 서브리스트를 삽입 정렬로 정렬하는 shellSort()의 보조 함수 j ← i + interval; while (j < n) do { new ← a[j]; // 서브리스트의 새로운 원소 k ← j; // new보다 큰 원소는 interval만큼 오른편으로 이동 move ← true; while (move) do { if (a[k – interval] ≤ new) then { move ← false; } else { a[k] ← a[k – interval]; k ← k – interval; if (k = i) then a[k] ← new; // 이동해서 생긴 자리에 삽입 j ← j + interval; // 다음 서브리스트 원소의 인덱스 end intervalSort()

10.7 쉘 정렬 (6) ShellSort의 C 구현 void shellSort(int a[], int size) {    int interval = size;    ……  /* ShellSort 알고리즘의 C 코드 */ ……    intervalSort(int_array, i, interval, size);    ……   /* 기타 C 코드 */ } void interval(int a[], int i, int interval, int size) {         /* 서브리스트를 삽입 정렬로 정렬하는 shellSort()의 보조 함수 */ ……. 

10.8 기수 정렬 (1) 기본 개념 정렬할 원소의 키값을 나타내는 숫자의 자리수(radix)를 기초로 정렬하는 기법(사전식 정렬) 80칼럼 천공 카드를 정렬시키거나 도서관 목록 카드 정렬과 같은 생활 응용에 많이 이용 방법 첫번째 패스 정렬할 키의 가장 작은 자리수를 기준으로 분배 정렬 두 번째 패스 두 번째 작은 자리수를 기준으로 분배 정렬 키 값이 같은 경우 이전 정렬에서의 순서를 그대로 유지 키의 가장 큰 자리수까지 반복 수행 시간 복잡도 : O(n)

10.8 기수 정렬 (2) RadixSort 알고리즘 radixSort(a[], n) for (k ← 1; k≤ m; k ← k+1) do { // m은 digit 수, k=1은 가장 작은 자리수 for (i ← 0; i < n; i ← i+1) do { kd ← kth-digit(a[i]); enqueue(Q[kd], a[i]); // Q[kd]에 a[i]를 삽입 } p ← -1; for (i ← 0; i ≤ 9; i ≤ i+1) do { while (Q[i] ≠ ) do { // Q[i]의 모든 원소를 a[]로 이동 p ← p+1; a[p] ← dequeue(Q[i]); end radixSort()

10.8 기수 정렬 (3) RadixSort 알고리즘 실행 단계 (a) 초기 리스트 : a = [35 81 12 67 93 46 23 26] Q[0] : [ ] Q[1] : [ 81 ] Q[2] : [ 12 ] Q[3] : [ 93 23 ] Q[4] : Q[5] : [ 35 ] Q[6] : [ 46 26 ] Q[7] : [ 67 ] Q[8] : Q[9] : Q[0] : [ ] Q[1] : [ 12 ] Q[2] : [ 23 26 ] Q[3] : [ 35 ] Q[4] : [ 46 ] Q[5] : Q[6] : [ 67 ] Q[7] : Q[8] : [ 81 ] Q[9] : [ 93 ] (b) 첫 번째 자리수를 기초로 정렬 • 결과 : [81 12 93 23 35 46 26 67] (c) 두 번째 자리수를 기초로 정렬 • 결과 : [12 23 26 35 46 67 81 93]

10.8 기수 정렬 (4) RadixSort의 C 구현 void radixSort(int a[], int size) { /* 기수 정렬의 함수 */ • • • • • // radixSort 알고리즘의 C 코드 }

10.9 트리 정렬 (1) 기본 개념 방법 이진 정렬 트리와 중위 우선 순회 방법을 사용한 정렬 방법 배열을 이진 정렬 트리에 삽입 동일한 키값의 원소 허용 루트와 같은 키값은 오른쪽 서브트리에 삽입 중위 우선 순회 방법으로 원소를 하나씩 검색하여 원래의 배열에 저장 시간 복잡도 : O(nlogn)

10.9 트리 정렬 (2) 트리 정렬 수행 예 (a) 초기 배열 a[] (b) 이진 정렬 트리 삽입 (c) 정렬된 배열 a[] [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 55 47 31 78 53 85 42 68 79 a[] : (a) 초기 배열 a[] 55 47 78 85 68 31 53 42 79 (b) 이진 정렬 트리 삽입 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 31 42 47 53 55 68 78 79 85 a[] : (c) 정렬된 배열 a[]

10.9 트리 정렬 (3) TreeSort 알고리즘 inorder 알고리즘 treeSort(a[], n) for (i ← 0; i < n; i ← i+1) insert(T, a[i]); // T는 이진 정렬 트리 inorder(T, a, -1); // inorder 알고리즘 end treeSort() inoder(T, a[], i) // treeSort()의 보조 함수 inorder(T.left, a, i); // T의 왼쪽 서브트리 i ← i+1 a[i] ← T.key; inorder(T.right, a, i); // T의 오른쪽 서브트리 end inorder()

Summary 10.1 선택 정렬 10.2 버블 정렬 10.3 삽입 정렬 10.4 합병 정렬 10.5 퀵 정렬 10.6 히프 정렬 10.7 쉘 정렬 10.8 기수 정렬 10.9 트리 정렬