퀵 정렬 (Quick sort)

▷ 퀵 정렬 (Quick Sort)

 정렬 알고리즘 중에 평균 실행 속도가 가장 빠르고 우수하므로 퀵 정렬(Quick sort)라는 명칭으로 불린다.

▷ 정렬방법.

1. 먼저 PIVOT 계수를 정한다. PIVOT 계수는 임의로 선정할 수 있으나, 중간 크기의 숫자를 PIVOT 계수로 선정하는 것이 가장 효율적이기 때문에 대부분 3개의 임의의 숫자를 랜덤으로 선택한 후 3개 중 가운데 값을 PIVOT 계수로 정한다.

2. PIVOT 값과 LEFT 값을 비교한다. 만약 LEFT 값이 PIVOT 값보다 크다면 PIVOT 값과 RIGHT 값을 비교한다.

RIGHT 값이 PIVOT 값보다 크다면, RIGHT 인덱스를 왼쪽으로 위치시킨 후 다시 PIVOT 값과 비교한다.

3. RIGHT 값이 PIVOT 값보다 작다면, LEFT 값과 RIGHT 값을 바꾼 후, LEFT 값을 오른쪽으로 한칸 전진시킨다.

4. LEFT 값과 RIGHT 값이 만날 때까지 2~3번 과정을 반복한다.

5. LEFT와 RIGHT가 만나면 해당 값과 PIVOT 값을 비교한다. PIVOT 값이 크면 오른 쪽 작으면 왼쪽에 위치 시킨다.

6. 3을 기준으로 블록을 크게 3보다 큰 값, 3보다 작은 값으로 나뉘게 된다. 3보다 작은 블록에 대해 다시 PIVOT 계수를 설정한다.

7. 기존에 한 방식대로 다시 LEFT와 RIGHT 값을 PIVOT과 비교한 후, 값을 교환한다.

8. 3보다 큰 블록에 대해서도 위와 같이 비교한다.

9. 최종 sorting이 완료된다.

Code.

#include <iostream>
using namespace std;
 
#define MAX            9
 
int Partition( int *Number, int Low, int High);
void QuickSort( int *Number, int Low, int High);
void Swap( int *_X, int *_Y);
 
void main()
{
    int Number[MAX] = {5,1,6,4,8,3,7,9,2};
 
    QuickSort( Number, 0, MAX - 1);
 
    for(int i = 0; i < MAX; i++)
        printf("%d \n", Number[i] );
}
 
void Swap( int *_X, int *_Y)
{
    int Temp = *_X;
    *_X = *_Y;
    *_Y = Temp;
}
 
void QuickSort( int *Number, int Low, int High)
{
    if(Low < High)
    {
        int Pivot = Partition( Number, Low, High);
        QuickSort( Number, Low, Pivot - 1);
        QuickSort( Number, Pivot + 1, High);
    }
}
 
int Partition( int *Number, int Low, int High)
{
    int Left = Low + 1;
    int Right = High;
    int Pivot = Number[Low];
 
    while( Left <= Right )
    {
        while( Number[Left] < Pivot && Left <= MAX - 1) Left++;
        while( Number[Right] > Pivot && Right >= 0 ) Right--;
 
        if(Left <= Right)
            Swap( &Number[Left], &Number[Right]);
    }
    Swap( &Number[Low], &Number[Right]);
    return Right;
}

결과