Sort - 정렬

아래 소개할 프로그램은 난수파일(input.txt)파일로부터 난수들을 사용자가 지정한 수 만큼 읽어 들여와서 Insert(삽입), Quick(빠른), Heap(힙), Merge(합병), Selection(선택), Bubble(버블) 별로 정렬하고 그 결과를 화면에 보여주고 각 정렬하는데 걸리는 시간을 측정하는 프로그램이다. 필자가 작성한 별도의 코드에는 정렬 과정도 출력하는 코드도 있지만 그건 이 코드를 아~~~주 조금만 손 보면 가능한 것이기에 따로 올리지는 않겠다. 그리고 이번에 새로 사용해보는 SyntaxHighlighter 관계상 코드의 복사가 가능함으로 주요 코드만 올리겠다. 우선 코드를 보면...

// 삽입 정렬 void Sort::insertsort() { int j=0; int i=1; // 삽입 정렬을 위한 변수 while(i<number) { j = i++; // 다음 값을 확인하기 위한 복사 while(j != 0) { if(i_array[j] > i_array[j-1]) // 이미 정렬된 상태라면 break; // break else // 전의 원소 크기가 더 크다면 교환 { temp = i_array[j]; i_array[j] = i_array[j-1]; i_array[j-1] = temp; j--; } } } } // 힙 정렬(배열의 첫 주소, 배열의 개수) void Sort::heapsort(int* h_temp, const int n) { for(int i=n/2; i>=1; i--) // 리스트를 히프로 전환 adjust(h_temp, i, n); // heap 모양이 되게 조정 for(i=n-1; i>=1; i--) // 리스트 정렬 { temp = h_temp[i+1]; // h_array[i+1], h_array[1] 교환 h_temp[i+1] = h_temp[1]; // 즉, n부터 가장 큰 순서대로 솔팅 h_temp[1] = temp; adjust(h_temp, 1, i); // sorting 후 heap tree 조정 } } void Sort::adjust(int* h_temp, const int root, const int n) // heap tree 구성 { int e = h_temp[root], j=0; for(j=2*root; j<=n; j*=2) { if(j<n) { if(h_temp[j]<h_temp[j+1]) j++; } if(e>=h_temp[j]) break; h_temp[j/2] = h_temp[j]; } h_temp[j/2] = e; } // 합병 정렬(배열의 첫 주소, 배열의 개수) void Sort::mergesort(int *m_temp, const int n) // 합병 정렬 { int* tempList = new int[n+1]; for(int l=1; l<n; l*=2) // l은 현재 합병되고 있는 서브리스트의 길이 { mergepass(m_temp, tempList, n, l); l *= 2; mergepass(tempList, m_temp, n, l); } delete[] tempList; } void Sort::merge(int* initList, int* mergedList, const int l, const int m, const int n) // 정렬된 두 리스트의 합병 { // [l:m] & [m+1:n]까지의 두개의 리스트를 [l:n] 리스트로 mergedList에 합병 for(int i1=l, iResult=l, i2=m+1; i1<=m && i2<=n; iResult++) { if(initList[i1]<=initList[i2]) mergedList[iResult] = initList[i1++]; else mergedList[iResult] = initList[i2++]; } copy(initList+i1, initList+m+1, mergedList+iResult); // 첫 번째 리스트의 나머지 복사(있다면) copy(initList+i2, initList+n+1, mergedList+iResult); // 두 번째 리스트의 나머지 복사(있다면) } void Sort::mergepass(int* initList, int* resultList, const int n, const int l) { for(int i=1; i<=n-2*l+1; i+=2*l) // (판단문)길이가 l인 두 서브리스트를 위해 원소들이 충분한지 비교 merge(initList, resultList, i, i+l-1, i+2*l-1); if((i+l-1)<n) merge(initList, resultList, i, i+l-1, n); // 2*l보다 작은 나머지 리스트들 합병 else copy(initList+i, initList+n+1, resultList+i); // 나머지 리스트들 복사(있다면) } // 퀵 정렬(배열의 가장 왼쪽 위치, 배열의 가장 오른쪽 위치) void Sort::quicksort(const int left, const int right) { if(left<right) { int i = left, j = right+1; int pivot = q_array[left]; do{ do i++; while(q_array[i]<pivot); // 가장 왼쪽부터 pivot까지 pivot보다 큰값 검색 do j--; while(q_array[j]>pivot); // 가장 오른쪽부터 pivot까지 pivot보다 작은값 검색 if(i<j) { temp = q_array[i]; // i와 j교환 q_array[i] = q_array[j]; q_array[j] = temp; } }while(i<j); temp = q_array[left]; // left와 j교환 q_array[left] = q_array[j]; q_array[j] = temp; quicksort(left, j-1); // 처음부터 j-1까지를 정리 quicksort(j+1, right); // j+1부터 마지막까지 정리 } } // 선택 정렬 void Sort::selectionsort() { int k=0; while(k++ < number-1) // 총 number 만큼을 정렬 { for(int i=0, j=0; i<number-k+1; i++) // 가장 큰 수를 찾아내는 반복문 if(s_array[j]<s_array[i]) j = i; // 가장 큰수 변경 temp = s_array[number-k]; // 마지막 값과 가장 큰 값 교환 s_array[number-k] = s_array[j]; s_array[j] = temp; } } // 버블 정렬 void Sort::bubblesort() { int j=number; while(j-->1) // 입력한 수-1 만큼 반복 for(int i=0; i<j; i++) if(b_array[i] > b_array[i+1]) { // 처음부터 한칸씩 이동하면서 다음 값이 더 크면 앞의 값과 교체 temp = b_array[i]; b_array[i] = b_array[i+1]; b_array[i+1] = temp; } }  

이렇다... 함수의 자세한 설명 및 기타 등등을 설명하기에는 너무 힘듬으로 알아서 보기를 바란다.(무책임해서 죄송 -_-) 그래도 예의상 가장 간단하지만 효율은 가장 안 좋은 Insert sort와 Selection sort와 bubble sort를 설명하겠다.

Insert sort(삽입 정렬)
- 기본 아이디어는 위의 코드를 보면 아시겠지만 앞에서 부터 하나씩 확인하는 것이다. 즉 i_array[0]과 i_array[1]를 비교하여 i_array[0]보다 i_array[1]이 크면 아무거도 안하고 반복문을 빠져나오다. 그 다음에 i_array[1]과 i_array[2]를 확인한다. 여기서 만약 i_array[2]가 i_array[1]보다 작다면 두개의 위치를 바꿔준다. 그리고 여기서 끝나는게 아니라 그 전의 값(i_array[0])과도 비교한다. 왜냐하면 비록 i_array[0]이 i_array[1]보다 작지만 그렇다고 새로 들어온 값인 i_array[2]보다도 작다는 보장이 없기 때문이다. 이런식으로 i_array[number](number은 사용자가 입력한 정렬할 원소의 개수)까지 확인을 하면 최종족으로 모든 i_array의 값이 정렬이 된다. 이것이 기본 아이디어다.

Selection sort(선택 정렬)
- 이것은 위의 Insert sort와 흡사하다. 방법은 배열 s_array[]의 0부터 number-1까지 확인하여 가장 큰 값을 찾는다. 그리고는 가장 마지막 위치(이때는 number-1이 된다.)과 교환해 준다. 그리고 다시 배열 s_array[]중에 가장 큰 값을 찾는데 범위가 위에와는 다르다. 가장 마지막 값(number-1)은 이미 가장 큰 값이 들어가 있기 때문에 확인할 필요가 없다.(라기보다 확인하면 안된다. 여기까지 확인을 하게 되면 결국 가장 큰거 하나만 가장 끝에 가있고 다른것은 하나도 정렬 안된다.) 즉 범위를 0부터 number-2까지 확인하여 현재의 가장 마지막 위치(이때는 number-2가 된다.)의 값과 교환한다. 이런 식으로 총 number-1번을 확인하게 되면 정렬이 완료된다.

Bubble sort(버블 정렬)
- 이것은 위의 2가지 방법과 유사하면서도 미묘하게 틀리다. 버블 정렬은 일단 가장 앞의 두개, 즉 b_array[0]과 b_array[1]을 확인하여 b_array[0]이 b_array[1]보다 크면 2개의 위치를 바꿔준다. 그리고는 b_array[1]과 b_array[2]를 확인하여 b_array[1]이 b_array[2]보다 크다면 다시 바꿔준다. 만약 크지 않다면 아무런 일도 하지 않고 그냥 넘어간다. 이런식으로 가다보면 마지막에는 b_array[number-2]와 b_array[number-1]를 비교하게 되고 이 결과 가장 큰 값이 가장 끝으로 오게 된다. 여기까지는 Selection sort와 비슷해 보이지만 아래 과정을 보면 차이를 알 수 있다. Selection sort는 오직 가장 큰 값만이 가장 마지막에 들어가는 반면 Bubble sort는 앞의 값들도 어느정도 정렬이 된다. 이런식으로 마지막 값을 number-1에서 number-2, number-3....... 하는 식으로 총 number-1번 비교하면 정렬된다. 덧붙이자면 필자가 이것저것 생각해본 결과 만약 오직 딱 한번만 정렬 과정을 수행하라고 한다면 Bubble sort가 그나마 가장 효율적인 방법이 아닐까 싶다.

위에 3개를 설명한 이유는 가장 간단하기 때문이다. 즉 선형시간이 소요된다. 한마디로 말해서 방법과 과정은 열라 단순한데 효율은 당연히 않좋다는 것이다. 위에 것은 어떻게 해도 O(n^2)만큼이 소요된다.

사실 필자도 이것을 작성하는데 상당한 시간과 노력이 필요했다. 저기서 필자가 자력으로 작성한 부분은 Insert sort 밖에 없다... 나머지는 부끄러운 얘기지만 책의 힘을 빌렸다. 위의 코드를 보면 알겠지만 Insert sort와 quick sort는 이해하는데 큰 무리는 없을 것이다. 기본적이 정렬 방식만 알고 있다면... 하지만 merge sort와 heap sort는 상당히 난해하다. 우선 정렬 방식이 인간의 사고방식과는 동떨어진 방식이기 때문이다. 하지만 찬찬히 훓터 보면 충분히 이해할 수 있을 것이다.
그리고 추가로 selection sort와 bubble sort를 추가하였다. 대충 왠만한 정렬은 다 있을 것이다. (물론 기수 정렬이라던지 다른것도 많~~이 있지만 왠만한건)

결과 화면을 보면...

요렇다. 즉, 앞의 Databace라고 써져 있는 부분이 난수 파일로부터 읽어 들여와 배열에 저장한 값이고 옆의 값들이 각 정렬별로 정렬한 결과를 표시한 부분이다. 10개 정도 밖에 안했기 때문에 시간은 다 0초라고 나온다. 필자가 확인해 본 결과 적어도 8000개 이상을 정렬하지 않으면 AMD Athlon(tm) 64 X2 Dual Core Processor TK-53 1.70GHz정도에서는 반응이 없을 것이다. 아니면 msec 단위로 찍으면 알 수 있을 것이다.

다음 화면은 아까 말한 정렬 과정을 보인 화면이다. 정렬 과정을 화면에 다 찍기에는 많아서 별도의 파일에 출력해서 얻었다. 앞의 i, m, h, q, s, b는 각각 insert, merge, heap, quick을 의미한다. 다 좋은데... 유일한 에러라고 한다면 quick sort일 것이다. 다른 것은 순서대로 내림차순으로 정렬되어 있지만 quick만은 이상하게 되어 있는 것을 확인 할 수있다. 저것도 필자가 5개만 정렬한 결과라 저정도지 한 100개 정렬하면 순서도 일정하지 않다. 저것을 어떻게 잘~~ 수정해 볼려고 하였지만 재귀함수 특성상 어쩔수 없었다는 비겁한 변명을 할 수 밖에 없다...

마지막으로 정렬을 하는 다른 사람을 위해 한마디 하자면... merge와 heap은 반드시 배열 [0]부터가 아닌 [1]부터 값을 저장하길 바란다... 필자도 저것 때문에 이틀 꼴아 박았다... ㅜ_ㅠ