DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다. 파일을 하나의 기준 값을 중심으로 두 개의 서브파일로 분할하여, 앞쪽의 파일 내의 모든 키는 뒤쪽의 파일 내의 어떤 키보다도 작도록 분할한다. 나누어진 서브파일에 대해서 동일한 방식의 분할을 서브파일의 크기가 1이 될 때까지 재귀적으로 수행하면 최종적으로 서브파일의 크기가 1이 되면 완전히 정렬된 상태의 파일이 구성된다.
2가지 파일 분할방식 0번째 키를 기준값으로 설정하는 방식 1번째 키부터 시작 2, 3번 방향으로 기준값보다 큰 키값을 만나면 그 키를 선택, n-1번째 키부터 시작 n-2, n-3번 방향으로 기준값보다 작은 키 값을 가진 키를 만나면 그 키를 선택하여 두 키 값을 교환한다. 선택되었던 두 키의 다음 위치에서부터 동일한 과정을 반복한다. 양쪽 방향에서 진행하는 순서가 교차하면 정지한다. 가장 나중에 선택한 기준 키 값보다 작은 키를 기준 키와 교환한다. 2. 기준 키 값을 파일내의 중간위치에 있는 키 값으로 설정하는 방식 기준 키 값의 앞에서 기준 키 값보다 큰 값을, 뒤에서 기준 키 값보다 작은 값을 선택하여 교환한다.
퀵 정렬은 하나의 파일을 두 개의 파일로 나누어질 때 두 서브 파일의 크기가 비슷하게 되면 비교의 횟수가 감소하게 된다 퀵 정렬은 하나의 파일을 두 개의 파일로 나누어질 때 두 서브 파일의 크기가 비슷하게 되면 비교의 횟수가 감소하게 된다. 그러나 두 서브파일의 크기의 차가 크거나 또는 아예 하나의 서브파일 밖에 만들어지지 않는 경우 수행시간이 길어진다. 예를 들어, 정렬하고자 하는 순서의 역순으로 데이터가 나열되어 있는 경우에는 서브파일이 항상 하나 밖에 생성되지 않는다.
퀵 정렬의 수행시간 • 평균 비교횟수가 nLog2n => O(nLog2n)
• 최악의 경우(서브파일이 하나만 존재) => O(n2) void quick_sort(int list[], int f, int n) { //f는 시작위치, n은 끝 위치 int i, j, k, temp; void quick_sort(int list[], int f, int n); void prnt(int list[]); if(f < n) { i=f+1; j=n; k=list[f]; //k는 기준값 if(i==j) { if(list[j] < k) { temp=list[j]; list[j]=k; list[f]=temp; } } while(i < j) { while((list[i] <= k) && (i<n)) i++; while(list[j] >= k && (j>f)) j--; if(i < j) { //기준값보다 큰, 작은 값을 교환 temp=list[i]; list[i]=list[j]; list[j]=temp; } } if(i > j) { temp=list[f]; //기준값과 교환 list[f]=list[j]; list[j]=temp; } quick_sort(list, f, j-1); //왼쪽 서브파일에 대해 반복 quick_sort(list, j+1, n); //오른쪽 서브파일에 대해 반복 } }
• 최악의 경우(서브파일이 하나만 존재) => O(n2)