The quicksort is considered to be
very efficient, with its "divide and
conquer" algorithm. This sort starts by dividing the original array into two
sections (partitions) based upon the value of the first element in the array.
Since our example sorts into descending order, the first section will contain
all the elements greater than the first element. The second section will
contain elements less than (or equal to) the first element. It is possible for
the first element to end up in either section.
Let's examine our same
example:
//Quick Sort
Functions for Descending Order
// (2 Functions)
void
QuickSort(apvector <int> &num, int top, int bottom)
{
// top = subscript of beginning of array
//
bottom = subscript of end of array
int middle;
if (top < bottom)
{
middle = partition(num, top, bottom);
quicksort(num,
top, middle); // sort first
section
quicksort(num, middle+1, bottom); // sort second
section
}
return;
}
//Function to determine the partitions
// partitions the array
and returns the middle subscript
int partition(apvector
<int> &array, int top, int bottom)
{
int x =
array[top];
int i = top - 1;
int j = bottom + 1;
int
temp;
do
{
do
{
j - -;
}while (x
>array[j]);
do
{
i++;
} while (x <array[i]);
if (i <
j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}while (i < j);
return j; // returns
middle subscript
}
※ 함수 설명
두 함수 모두 비재귀 형식의 퀵소트이며
- quick_sort1() 함수는 : 세값의 중위 분할을 통한 퀵소트로, 삽입정렬을 사용한다.
- quick_sort2() 함수는 : 난수 분할을 통한 퀵소트이며, 삽입정렬을 사용한다.
이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.
■ 퀵 정렬 개념
주어진 입력 리스트를 피봇(pivot) 또는 제어키(control key)이라 불리는 특정 키 값보다 작은 값을 가지는 레코드들의 리스트와 큰 값을 가지는 레코드들의 리스트로 분리한 다음, 이러한 두 개의 서브 리스트들을 재귀적으로 각각 재배열하는 과정을 수행하는 방식
퀵 정렬 방법은 하나의 커다란 입력 데이터의 집합을 정렬하는 것보다는 두개의 작은 입력 데이터들을 정렬하는 것이 빠르다는 일반적인 사실에 바탕을 둠
분할 및 정복 방법 사용
피봇(Pivot)이라 부르는 특정한 데이터를 기준으로 피봇보다 작은 값을 가진 데이터들은
배열의 왼쪽 부분에, 큰 값을 가진 데이터는 오른쪽에 위치하도록 배열
퀵 정렬은 기본적으로 순환(recursive) 알고리즘 형태를 취하며, 오름차순으로 정렬할 경우 레코드 R1을 제어 키 또는 피봇 키로 하여 왼쪽으로 가면서 R1보다 큰 키 값을 찾고, 오른쪽으로부터 왼쪽으로 가면서 R1보다 작은 키 값을 찾아 서로 교환한다. 위의 과정이 수행될 때 오른쪽과 왼쪽이 서로 교차하면 중지하고 R1을 제일 나중에 찾은 R1보다 작은 키 값과 교환하면 R1보다 작은 키 값을 갖는 레코드들과 큰 키 값을 갖는 레코드들로 분할되어 하나의 파일이 제어키 R1을 기준으로 두 개의 서브 파일로 재배열된다. 재배열된 서브파일에 대해 독립적으로 위의 수행 과정을 반복하면 정렬이 완료된다.
■ 퀵 정렬 알고리즘 단계 : 분할과 정복 방식
① 피봇(Pivot) : 정렬할 데이터 S에서 하나 v를 선택한다.
② 분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
③ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}
■ 특징
▷ 평균 연산 시간에 있어서 내부 정렬 방법 중 가장 우수
- 실제 수행속도가 가장 빠른 정렬 알고리즘
▷ 스택 공간을 사용
▷ 재귀 호출을 기반으로 동작
■ 퀵 정렬 알고리즘
-----------------------------------------------------------------------------
void Quicksort(int A[], int N) {Qsort(A,0, N-1); } /* 퀵 정렬 호출 함수 */
int Median3(int A[], int Left, int Right) /* 세 수의 중위수 계산 함수 */
{ int Center= (Left + Right) / 2; /* A[Left]<= A[Center]<= A[Right]*/
lf( A[Left] > A[Center] ) Swap( &A[Left], &A[Center] );
if( A[Left] > A[Right] ) Swap( &A[Left], &A[Right] );
if( A[Center] > A[Right]) Swap(&A[Center], &A[Right]);
swap( &A[Center], &A[Right-1] ); /* 피봇된 수를 오른쪽-1의 위치에 있는 수와 SWAP */
return A[Right-1]; /*return 피봇 */
}
#define Cutoff(3) /* 퀵 정렬 함수 */
void Qsort( int A[], int Left, int Right ) /* 배열 A의 왼쪽 끝 첨자:Left, 오른쪽 끝 첨자:Right */
{ int i, j, Pivot;
/*1*/ if( Left + Cutoff <= Right )
/*2*/ { Pivot = Median3( A, Left, Right);
/*3*/ i=Left; j=Right-1;
/*4*/ for( ; ; )
/*5*/ { while( A[++i ] < Pivot ){}
/*6*/ while( A[--j ] > Pivot ){}
/*7*/ if( i < j )
/*8*/ swap( &A[ i ], &A[ j ] );
/*9*/ else break;
}
/*10*/ swap( &A[ i ], &A[ Right-1] );
/*11*/ Qsort( A, Left, i-1 );
/*12*/ Qsort( A, i+1, Right );
}
else
/*13*/ InsertionSort( A+Left , Right-Left+1)
}
②세 수의 중위수 계산, Pivot에 중앙값 넣기
⑤배열의 왼쪽에서부터 중앙값보다 큰 원소까지
이동
⑥배열의 오른쪽에서부터 원소의 값이 중앙값보다
작은 원소까지 이동
⑦⑧⑨정렬이 끝나지 않았으면 중앙값보다 작은
원소는 왼쪽에, 큰 원소는 오른쪽에 들어가도록
교체함. 정렬이 끝났으면 무한루프를 벗어남
⑩중앙값보다 큰 첫 번째 요소와 중앙값을 교환해
중앙값을 작은 값과 큰 값 사이에 끼워 넣음.
중위치 정렬
⑪왼쪽부분리스트(중앙값보다 작은부분)의 퀵정렬
⑫오른쪽부분리스트(중앙값보다 큰부분)의 퀵정렬
⑬원소가 Cutoff보다 작거나 같은 서브트리의
삽입정렬
-----------------------------------------------------------------------------
■ 성능
▷ 최악의 경우: O(n2)
▷ 평균: O(nlogn)
▷ 최선의 경우는 n 개의 데이터가 저장된 배열이 각 분할 단계에서 정확히 이등분 될 때
▷ 교환 및 비교 회수가 매우 적음 : 단순하고 매우 빠른 속도로 수행
▷ 안정성은 없음
▷ 난수 배열 및 반쯤 정렬된 배열 자료에 대해서는 성능이 우수
▷ 피봇이 중간 값을 갖도록 해야 수행속도가 좋아짐