|
-----------------------------------------------------------------------------
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)
}
-----------------------------------------------------------------------------
|
