Quick Sort
Quick 정렬은 버블정렬과 함께, 가장 쉽게 응용할 수 있는 정렬기법이다. 평균적으로 O(n log n)번의 비교를 수행하며, 최악의 경우에 O(n^2)의 비교를 수행하도록 되어 있다.
정렬할 데이터가 이미 준비되어 있으며, 모든 데이터를 정렬해야 할경우 가장 빠른 수행속도를 보여주는 알고리즘으로 평가되고 있다.
퀵정렬은 다음과 같은 방식으로 진행이 된다.
- 주어진 데이터 목록에서 임의의 원소를 고른다. 이 원소를 피봇이라 한다.
- 피봇을 기준으로 피봇의 앞에는 피봇보다 작은 숫자가 오도록 하고, 피봇 뒤에는 피봇보다 큰 원소가 오도록한다. 필요할 경우 피봇은 움지일 수 있다.
- 1,2의 과정을 재귀수행한다. 한번의 피봇이 선택되어서 분할이 이루어질 때마다. 반드시 고정되는 값이 생성이 되므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
위의 프로세스가 퀵소트 알고리즘의 핵심으로 머리속으로 이해했다면, 구현하는 것도 그리 어렵지 않을 것이다. 구현에도 몇가지 방법이 있는데, 그 중에서 별도의 버퍼를 필요로 하지 않는 내부분할 퀵소트가 널리 사용되고 있다. 이 방법은 정렬을 위한 임시버퍼를 필요로 하지 않으므로 메모리를 할당하고 유지하기 위한 비용을 고려할 필요가 없다는 장점이 있다.
다음은 C로 작성된 퀵정렬 알고리즘이다.
void quickSort(int numbers[], int array_size); void q_sort(int numbers[], int left, int right); void quickSort(int numbers[], int array_size) { q_sort(numbers, 0, array_size -1); } void q_sort(int numbers[], int left, int right) { int pivot, l_hold, r_hold; l_hold = left; r_hold = right; pivot = numbers[left]; // 0번째 원소를 피봇으로 선택 while (left < right) { // 값이 선택한 피봇과 같거나 크다면, 이동할 필요가 없다 while ((numbers[right] >= pivot) && (left < right)) right --; // 그렇지 않고 값이 피봇보다 작다면, // 피봇의 위치에 현재 값을 넣는다. if (left != right) { numbers[left] = numbers[right]; } // 왼쪽부터 현재 위치까지 값을 읽어들이면서 // 피봇보다 큰 값이 있다면, 값을 이동한다. while ((numbers[left] <= pivot) && (left < right)) left ++; if (left != right) { numbers[right] = numbers[left]; right --; } } // 모든 스캔이 끝났다면, 피봇값을 현재 위치에 입력한다. // 이제 피봇을 기준으로 왼쪽에는 피봇보다 작거나 같은 값만 남았다. numbers[left] = pivot; pivot = left; left = l_hold; right = r_hold; // 재귀호출을 수행한다. if (left < pivot) q_sort(numbers, left, pivot - 1); if (right > pivot) q_sort(numbers, pivot+1, right); } int main(int argc, char **argv) { int data[] = {3,7,8,5,2,1,9,5,4}; int i; quickSort(data, 9); for (i =0; i < 9; i++) { printf("%d\n", data[i]); } }
'Language > C Programming' 카테고리의 다른 글
C programming :: 키 채터링 방지 키 체크 함수 (0) | 2011.12.19 |
---|---|
C programming :: 전처리기 매크로 치환 (0) | 2011.12.19 |
C programming :: Ring Buffer (0) | 2011.12.19 |
C programming :: 매크로를 이용한 메모리 직접 접근 방법 (0) | 2011.12.19 |
C Programming :: Void형 포인터와 NULL 포인터 (0) | 2011.12.19 |
아무리 뛰어난 정렬 알고리즘(:12)을 개발한다고 하더라도, 데이터의 갯수가 N이면 O(NlogN)보다 더 좋을 수
없다는 것이 증명되어 있다.
즉 정렬알고리즘의 lower bound는 O(NlogN)이다.
단 최대값이 정해져 있는 데이터라면 counting 방식을 쓸수 있고 - counting sort, bucket sort, radix sort - 이 경우 O(n)이 보장될 것이다.