10장 정렬(Sorting)

단순 정렬 알고리즘

1. 버블 정렬(Bubble Sort) : O(n2)
2. 선택 정렬(Selection Sort) : O(n2)
3. 삽입 정렬(Insertion Sort) : O(n2)

복잡하지만 효율적인 정렬 알고리즘

1. 힙 정렬(Heap Sort) : O(nlog2n)
2. 병합 정렬(Merge Sort) : O(nlog2n)
3. 퀵 정렬(Quick Sort) : O(nlog2n)
4. 기수 정렬(Radix Sort) : O(ln) -> O(n)

예상문제 : {13, 212, 14, 7141, 10987, 6, 15}

1. 버블 정렬 2회전한 후의 결과는?
2. 선택 정렬 3회전한 후의 결과는?
3. 삽입 정렬 4회전한 후의 결과는?
4. 힙 정렬을 위해 최소힙(Min Heap)을 구성한 후 2개 삭제 후의 힙을 그리시오.
5. 병합정렬 과정을 단계별로 그리시오.
6. 퀵정렬 과정을 단계별로 그리시오.
7. 버킷 5개를 가지고 기수 정렬(LSD) 과정을 단계별로 그리시오.
   1. 버킷을 5개 가지고 하려면 5진수로 변경해서 풀어야 함(현재 수준으로는 어려움)
   2. 이번 퀴즈는 버킷 10개 중 0,1,2,3,4번만 가지고 풀 수 있는 문제로 출제했음

소스 코드

1. 버블 정렬(Bubble Sort)  : S010_BubbleSort.c
   
   #include <stdio.h> void BubbleSort(int arr[], int n){ int i, j; int temp; for(i=0; i<n-1; i++){ for(j=0; j<(n-i)-1; j++){ if(arr[j] > arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } int main(void){ int arr[4] = {3, 2, 4, 1}; int i; BubbleSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

   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

   #include <stdio.h>   void BubbleSort(int arr[], int n){ int i, j; int temp;   for(i=0; i<n-1; i++){ for(j=0; j<(n-i)-1; j++){ if(arr[j] > arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }   int main(void){ int arr[4] = {3, 2, 4, 1}; int i;   BubbleSort(arr, sizeof(arr)/sizeof(int));   for(i=0; i<4; i++) printf("%d ", arr[i]);   printf("\n"); return 0; }

2. 선택 정렬(Selection Sort) : S010_SelectionSort.c
   
   #include <stdio.h> void SelSort(int arr[], int n){ int i, j; int maxIdx; int temp; for(i=0; i<n-1; i++){ maxIdx = i; // 정렬 순서상 가장 앞서는 데이터의 index for(j=i+1; j<n; j++){ // 최소값 탐색 if(arr[j] < arr[maxIdx]) maxIdx = j; } /* 교환 */ temp = arr[i]; arr[i] = arr[maxIdx]; arr[maxIdx] = temp; } } int main(void){ int arr[4] = {3, 4, 2, 1}; int i; SelSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<4; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

   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

   #include <stdio.h>   void SelSort(int arr[], int n){ int i, j; int maxIdx; int temp;   for(i=0; i<n-1; i++){ maxIdx = i;    // 정렬 순서상 가장 앞서는 데이터의 index   for(j=i+1; j<n; j++){  // 최소값 탐색 if(arr[j] < arr[maxIdx]) maxIdx = j; } /* 교환 */ temp = arr[i]; arr[i] = arr[maxIdx]; arr[maxIdx] = temp; } }   int main(void){ int arr[4] = {3, 4, 2, 1}; int i;   SelSort(arr, sizeof(arr)/sizeof(int));   for(i=0; i<4; i++) printf("%d ", arr[i]);   printf("\n"); return 0; }

3. 삽입 정렬(Insertion Sort) : S010_InsertionSort.c
   
   #include <stdio.h> void InserSort(int arr[], int n){ int i, j; int insData; for(i=1; i<n; i++){ insData = arr[i]; // 정렬 대상을 insData에 저장 for(j=i-1; j>=0 ; j--){ if(arr[j] > insData) arr[j+1] = arr[j]; // 비교 대상 한 칸 뒤로 밀기 else break; // 삽입 위치 찾았으니 탈출! } arr[j+1] = insData; // 찾은 위치에 정렬 대상 삽입! } } int main(void){ int arr[5] = {5, 3, 2, 4, 1}; int i; InserSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<5; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

   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

   #include <stdio.h>   void InserSort(int arr[], int n){ int i, j; int insData;   for(i=1; i<n; i++){ insData = arr[i];   // 정렬 대상을 insData에 저장   for(j=i-1; j>=0 ; j--){ if(arr[j] > insData) arr[j+1] = arr[j];    // 비교 대상 한 칸 뒤로 밀기 else break;   // 삽입 위치 찾았으니 탈출! }   arr[j+1] = insData;  // 찾은 위치에 정렬 대상 삽입! } }   int main(void){ int arr[5] = {5, 3, 2, 4, 1}; int i;   InserSort(arr, sizeof(arr)/sizeof(int));   for(i=0; i<5; i++) printf("%d ", arr[i]);   printf("\n"); return 0; }

4. 힙 정렬(Heap Sort) : S010_HeapSort.c
   
   #include <stdio.h> #define TRUE 1 #define FALSE 0 #define HEAP_LEN 100 int numOfData; int heap[HEAP_LEN]; void HeapInit(){ numOfData = 0; } int HIsEmpty(){ if(numOfData == 0) return TRUE; else return FALSE; } int GetParentIDX(int idx) { return idx/2; } int GetLChildIDX(int idx){ return idx*2; } int GetRChildIDX(int idx){ return GetLChildIDX(idx)+1; } int GetHiPriChildIDX(int idx){ if(GetLChildIDX(idx) > numOfData){ // 자식 노드가 없다면 return 0; } else if(GetLChildIDX(idx) == numOfData){ // 왼쪽 자식 노드가 마지막 노드라면 return GetLChildIDX(idx); } else{ // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교 if(heap[GetLChildIDX(idx)] > heap[GetRChildIDX(idx)]) return GetRChildIDX(idx); else return GetLChildIDX(idx); } } void HInsert(int pr){//root노드의 idx = 1 int idx = numOfData + 1; int nelem = pr; while(idx != 1){ if(pr < (heap[GetParentIDX(idx)])){ heap[idx] = heap[GetParentIDX(idx)]; idx = GetParentIDX(idx); } else{ break; } } heap[idx] = nelem; numOfData += 1; } char HDelete() { char retData = heap[1]; // 삭제할 데이터 임시 저장 int lastElem = heap[numOfData]; int parentIdx = 1; // 루트 노드의 Index int childIdx; while(childIdx = GetHiPriChildIDX(parentIdx)) { if(lastElem <= heap[childIdx]) break; heap[parentIdx] = heap[childIdx]; parentIdx = childIdx; } heap[parentIdx] = lastElem; numOfData -= 1; return retData; } void HeapSort(int arr[], int n){ int i; HeapInit(); // 정렬 대상을 가지고 힙을 구성한다. for(i=0; i<n; i++) HInsert(arr[i]); // 순서대로 하나씩 꺼내서 정렬을 완성한다. for(i=0; i<n; i++) arr[i] = HDelete(); } int main(void) { int arr[8] = {3, 4, 2, 1, 7, 6, 9,5}; int i; HeapSort(arr, sizeof(arr)/sizeof(int)); for(i=0; i<sizeof(arr)/sizeof(int); i++) printf("%d ", arr[i]); printf("\n"); return 0; }

   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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

   #include <stdio.h>   #define TRUE 1 #define FALSE 0   #define HEAP_LEN 100   int numOfData; int heap[HEAP_LEN];   void HeapInit(){ numOfData = 0; }   int HIsEmpty(){ if(numOfData == 0) return TRUE; else return FALSE; }   int GetParentIDX(int idx) { return idx/2; }   int GetLChildIDX(int idx){ return idx*2; }   int GetRChildIDX(int idx){ return GetLChildIDX(idx)+1; }   int GetHiPriChildIDX(int idx){ if(GetLChildIDX(idx) > numOfData){    // 자식 노드가 없다면 return 0; } else if(GetLChildIDX(idx) == numOfData){    // 왼쪽 자식 노드가 마지막 노드라면 return GetLChildIDX(idx); } else{   // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교 if(heap[GetLChildIDX(idx)] > heap[GetRChildIDX(idx)]) return GetRChildIDX(idx); else return GetLChildIDX(idx); } }   void HInsert(int pr){//root노드의 idx = 1 int idx = numOfData + 1; int nelem = pr;   while(idx != 1){ if(pr < (heap[GetParentIDX(idx)])){ heap[idx] = heap[GetParentIDX(idx)]; idx = GetParentIDX(idx); } else{ break; } }   heap[idx] = nelem; numOfData += 1; }   char HDelete() { char retData = heap[1];    // 삭제할 데이터 임시 저장 int lastElem = heap[numOfData];   int parentIdx = 1;    // 루트 노드의 Index int childIdx;   while(childIdx = GetHiPriChildIDX(parentIdx)) { if(lastElem <= heap[childIdx]) break;   heap[parentIdx] = heap[childIdx]; parentIdx = childIdx; }   heap[parentIdx] = lastElem; numOfData -= 1; return retData; }   void HeapSort(int arr[], int n){ int i;   HeapInit();   // 정렬 대상을 가지고 힙을 구성한다. for(i=0; i<n; i++) HInsert(arr[i]);   // 순서대로 하나씩 꺼내서 정렬을 완성한다. for(i=0; i<n; i++) arr[i] = HDelete(); }   int main(void) { int arr[8] = {3, 4, 2, 1, 7, 6, 9,5}; int i;   HeapSort(arr, sizeof(arr)/sizeof(int));   for(i=0; i<sizeof(arr)/sizeof(int); i++) printf("%d ", arr[i]);   printf("\n"); return 0; }

5. 병합 정렬(Merge Sort) : S010_MergeSort.c
   
   #include <stdio.h> #include <stdlib.h> void MergeTwoArea(int arr[], int left, int mid, int right){ int fIdx = left; int rIdx = mid+1; int i; int * sortArr = (int*)malloc(sizeof(int)*(right+1)); int sIdx = left; while(fIdx<=mid && rIdx<=right){ if(arr[fIdx] <= arr[rIdx]) sortArr[sIdx] = arr[fIdx++]; else sortArr[sIdx] = arr[rIdx++]; sIdx++; } if(fIdx > mid){ for(i=rIdx; i<=right; i++, sIdx++) sortArr[sIdx] = arr[i]; } else{ for(i=fIdx; i<=mid; i++, sIdx++) sortArr[sIdx] = arr[i]; } for(i=left; i<=right; i++) arr[i] = sortArr[i]; free(sortArr); } void MergeSort(int arr[], int left, int right){ int mid; if(left < right){ // 중간 지점을 계산한다. mid = (left+right) / 2; // 둘로 나눠서 각각을 정렬한다. MergeSort(arr, left, mid); MergeSort(arr, mid+1, right); // 정렬된 두 배열을 병합한다. MergeTwoArea(arr, left, mid, right); } } int main(void){ int arr[7] = {3, 2, 4, 1, 7, 6, 5}; int i; // 배열 arr의 전체 영역 정렬 MergeSort(arr, 0, sizeof(arr)/sizeof(int)-1); for(i=0; i<7; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

   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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

   #include <stdio.h> #include <stdlib.h>   void MergeTwoArea(int arr[], int left, int mid, int right){ int fIdx = left; int rIdx = mid+1; int i;   int * sortArr = (int*)malloc(sizeof(int)*(right+1)); int sIdx = left;   while(fIdx<=mid && rIdx<=right){ if(arr[fIdx] <= arr[rIdx]) sortArr[sIdx] = arr[fIdx++]; else sortArr[sIdx] = arr[rIdx++];   sIdx++; }   if(fIdx > mid){ for(i=rIdx; i<=right; i++, sIdx++) sortArr[sIdx] = arr[i]; } else{ for(i=fIdx; i<=mid; i++, sIdx++) sortArr[sIdx] = arr[i]; }   for(i=left; i<=right; i++) arr[i] = sortArr[i];   free(sortArr); }   void MergeSort(int arr[], int left, int right){ int mid;   if(left < right){ // 중간 지점을 계산한다. mid = (left+right) / 2;   // 둘로 나눠서 각각을 정렬한다. MergeSort(arr, left, mid); MergeSort(arr, mid+1, right);   // 정렬된 두 배열을 병합한다. MergeTwoArea(arr, left, mid, right); } }   int main(void){ int arr[7] = {3, 2, 4, 1, 7, 6, 5}; int i;   // 배열 arr의 전체 영역 정렬 MergeSort(arr, 0, sizeof(arr)/sizeof(int)-1);   for(i=0; i<7; i++) printf("%d ", arr[i]);   printf("\n"); return 0; }

6. 퀵 정렬(Quick Sort) : S010_QuickSort.c
   
   #include <stdio.h> void Swap(int arr[], int idx1, int idx2){ int temp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = temp; } int Partition(int arr[], int left, int right){ int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽! int low = left+1; int high = right; while(low <= high){ // 교차되지 않을 때까지 반복 while(pivot > arr[low]) low++; while(pivot < arr[high]) high--; if(low <= high) // 교차되지 않은 상태라면 Swap 실행 Swap(arr, low, high); // low와 high가 가리키는 대상 교환 } Swap(arr, left, high); // 피벗과 high가 가리키는 대상 교환 return high; // 옮겨진 피벗의 위치 정보 반환 } void QuickSort(int arr[], int left, int right){ if(left <= right){ int pivot = Partition(arr, left, right); // 둘로 나눠서 QuickSort(arr, left, pivot-1); // 왼쪽 영역을 정렬 QuickSort(arr, pivot+1, right); // 오른쪽 영역을 정렬 } } int main(void){ int arr[7] = {3, 2, 4, 1, 7, 6, 5}; // int arr[3] = {3, 3, 3}; int len = sizeof(arr) / sizeof(int); int i; QuickSort(arr, 0, sizeof(arr)/sizeof(int)-1); for(i=0; i<len; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

   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 44 45 46 47 48 49 50 51

   #include <stdio.h>   void Swap(int arr[], int idx1, int idx2){ int temp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = temp; }   int Partition(int arr[], int left, int right){ int pivot = arr[left];    // 피벗의 위치는 가장 왼쪽! int low = left+1; int high = right;   while(low <= high){     // 교차되지 않을 때까지 반복 while(pivot > arr[low]) low++;   while(pivot < arr[high]) high--;   if(low <= high)    // 교차되지 않은 상태라면 Swap 실행 Swap(arr, low, high);    // low와 high가 가리키는 대상 교환 }   Swap(arr, left, high);    // 피벗과 high가 가리키는 대상 교환 return high;    // 옮겨진 피벗의 위치 정보 반환 }   void QuickSort(int arr[], int left, int right){ if(left <= right){ int pivot = Partition(arr, left, right);    // 둘로 나눠서 QuickSort(arr, left, pivot-1);    // 왼쪽 영역을 정렬 QuickSort(arr, pivot+1, right);    // 오른쪽 영역을 정렬 } }   int main(void){ int arr[7] = {3, 2, 4, 1, 7, 6, 5}; // int arr[3] = {3, 3, 3};   int len = sizeof(arr) / sizeof(int); int i;   QuickSort(arr, 0, sizeof(arr)/sizeof(int)-1);   for(i=0; i<len; i++) printf("%d ", arr[i]);   printf("\n"); return 0; }

7. 기수 정렬(Radix Sort) : S010_RadixSort.c, LSD 기준
   
   #include <stdio.h> #include <stdlib.h> #define BUCKET_NUM 10 typedef struct _node{ int data; struct _node * next; } Node; Node *front[BUCKET_NUM]; Node *rear[BUCKET_NUM]; ////// queue의 기본함수 enqueue(), dequeue(), +알파함수 peek() void enqueue(int buck_no, int data){ Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = data; newNode->next = NULL; if(front[buck_no] == NULL){ front[buck_no] = newNode; rear[buck_no] = newNode; } else{ rear[buck_no]->next = newNode; rear[buck_no] = newNode; } } int dequeue(int buck_no){ int data = -1; if(front[buck_no] == NULL){ printf("Empty\n"); } else{ Node *cur = front[buck_no]; data = cur->data; front[buck_no] = cur->next; free(cur); } return data; } int peek(int buck_no){ if(front[buck_no] == NULL){ printf("Empty\n"); return -1; } else{ return front[buck_no]->data; } } ////////// stack 추가 함수 void initQueue(int buck_no){ front[buck_no] = NULL; rear[buck_no] = NULL; } int isEmpty(int buck_no){ if(front[buck_no] == NULL){ return 1; //true } else{ return 0; //false } } void Free(){ int i; Node *cur; for(i=0; i<BUCKET_NUM; i++){ while(front[i] != NULL) { cur = front[i]; front[i] = front[i]->next; free(cur); } } } ///////// 메인 함수 void RadixSort(int arr[], int num, int maxLen){ // maxLen은 가장 긴 데이터의 길이 int bi; int pos; int di; int divfac = 1; int radix; // 총 10개의 버킷 초기화 for(bi=0; bi<BUCKET_NUM; bi++) initQueue(bi); // 가장 긴 데이터의 길이만큼 반복 for(pos=0; pos<maxLen; pos++){ // 정렬 대상의 수만큼 반복 for(di=0; di<num; di++){// N번째 자리의 숫자 추출 radix = (arr[di] / divfac) % 10; // 추출한 숫자를 근거로 데이터 버킷에 저장 enqueue(radix, arr[di]); } // 버킷 수만큼 반복 for(bi=0, di=0; bi<BUCKET_NUM; bi++){ // 버킷에 저장된 것 순서대로 다 꺼내서 다시 arr에 저장 while(!isEmpty(bi)) arr[di++] = dequeue(bi); } // N번째 자리의 숫자 추출을 위한 피제수의 증가 divfac *= 10; } } int main(void){ int arr[7] = {13, 212, 14, 7141, 10987, 6, 15}; int len = sizeof(arr) / sizeof(int); int i; RadixSort(arr, len, 5); for(i=0; i<len; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

   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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

   #include <stdio.h> #include <stdlib.h>   #define BUCKET_NUM 10   typedef struct _node{ int data; struct _node * next; } Node;   Node *front[BUCKET_NUM]; Node *rear[BUCKET_NUM];   ////// queue의 기본함수 enqueue(), dequeue(), +알파함수  peek() void enqueue(int buck_no, int data){ Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = data; newNode->next = NULL; if(front[buck_no] == NULL){ front[buck_no] = newNode; rear[buck_no] = newNode; } else{ rear[buck_no]->next = newNode; rear[buck_no] = newNode; } }   int dequeue(int buck_no){ int data = -1; if(front[buck_no] == NULL){ printf("Empty\n"); } else{ Node *cur = front[buck_no]; data = cur->data; front[buck_no] = cur->next; free(cur); } return data; }   int peek(int buck_no){ if(front[buck_no] == NULL){ printf("Empty\n"); return -1; } else{ return front[buck_no]->data; } }   ////////// stack 추가 함수   void initQueue(int buck_no){ front[buck_no] = NULL; rear[buck_no] = NULL; }   int isEmpty(int buck_no){ if(front[buck_no] == NULL){ return 1; //true } else{ return 0; //false } }   void Free(){ int i; Node *cur;   for(i=0; i<BUCKET_NUM; i++){ while(front[i] != NULL) { cur = front[i]; front[i] = front[i]->next; free(cur); } } }   ///////// 메인 함수   void RadixSort(int arr[], int num, int maxLen){   // maxLen은 가장 긴 데이터의 길이 int bi; int pos; int di; int divfac = 1; int radix;   // 총 10개의 버킷 초기화 for(bi=0; bi<BUCKET_NUM; bi++) initQueue(bi);   // 가장 긴 데이터의 길이만큼 반복 for(pos=0; pos<maxLen; pos++){ // 정렬 대상의 수만큼 반복 for(di=0; di<num; di++){// N번째 자리의 숫자 추출 radix = (arr[di] / divfac) % 10;   // 추출한 숫자를 근거로 데이터 버킷에 저장 enqueue(radix, arr[di]); }   // 버킷 수만큼 반복 for(bi=0, di=0; bi<BUCKET_NUM; bi++){ // 버킷에 저장된 것 순서대로 다 꺼내서 다시 arr에 저장 while(!isEmpty(bi)) arr[di++] = dequeue(bi); }   // N번째 자리의 숫자 추출을 위한 피제수의 증가 divfac *= 10; } }   int main(void){ int arr[7] = {13, 212, 14, 7141, 10987, 6, 15};   int len = sizeof(arr) / sizeof(int); int i;   RadixSort(arr, len, 5);   for(i=0; i<len; i++) printf("%d ", arr[i]);   printf("\n"); return 0; }