정렬(Sort) : 빠른정렬, 퀵 소트(Quick Sort)

정렬에 대한 세번째 포스팅으로 빠른 정렬, 퀵 소트에 대해서 알아보겠습니다.

이전 게시글 )

정렬(Sort) : 삽입정렬(Insertion Sort) : http://andrew0409.tistory.com/138

파이썬 예제 : 리스트를 정렬(Sort)하는 여러가지 방법 : http://andrew0409.tistory.com/65

파이썬 예제 : 튜플(Tuple)을 정렬(Sort)하는 여러가지 방법 : http://andrew0409.tistory.com/66

퀵 정렬(quick sort)은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법입니다. 퀵 정렬은 재귀적으로 실행되기 때문에 재귀 함수에 대한 충분한 이해가 없으신 분들은 재귀함수에 대해 정리해 놓은 이전 포스팅을 보고 오시기 바랍니다.

자료구조 : 재귀함수(Recursive Function) : http://andrew0409.tistory.com/145.

난수열에 대해 퀵 정렬을 실행한 그림. 수평선은 피벗 값을 가리킨다.

그림을 잘 보시면 알 수 있듯이, 임의의 피벗값을 정의해놓고, 피벗값보다 작은값은 중간의 앞부분으로, 큰값은 중간보다 뒤로 보내버립니다.

이렇게 범위를 반으로 쪼개어 가며 정렬을 하게 되기 때문에 재귀적인 코딩이 필요합니다.

흐름(알고리즘)에 대해서 순서대로 설명하겠습니다.

1. 임의의 데이터 집합에서 하나의 데이터를 고릅니다. 이것을 피벗(pivot)이라고 합니다.

2. 피벗 앞에는 피벗보다 작은 데이터들이 모이고, 피벗 뒤에는 피벗보다 큰 데이터들이 모입니다. 이렇게 피벗을 기준으로 데이터 집합을 둘로 나눕니다. 이와 같은 과정을 진행하는 동안 피벗은 움직이지 않습니다.

3. 반으로 나뉜 데이터 집합에 대해 재귀적으로 반복하며, 데이터의 갯수가 0이나 1이 될때까지 반복합니다.

재귀호출이 한번 일어날때 마다 최소한 하나의 원소는 최종적인 자리가 정해지게 되므로 이 알고리즘은 반드시 끝나는 것을 보장합니다.

5 - 3 - 7 - 6 - 2 - 1 - 4 
p

int array[7] = {5, 3, 7, 6, 2, 1, 4};
int pivot = array[0];

5, 3, 7, 6, 2, 1, 4 이와 같이 만들어진 배열이 있습니다. p는 피벗의 위치 L,R로 왼쪽 오른쪽에서 출발하는 인덱스를 표시하겠습니다.

5 - 3 - 7 - 6 - 2 - 1 - 4 
p   L                   R

int L = array[1], R = sizeof(array)/sizeof(array[0] - 1);

피벗이 배열의 0번방에 있으므로 L은 1번 인덱스부터 시작하며, R은 마지막 방의 인덱스에서 시작합니다.

sizeof 는 전달인자의 데이터 크기를 계산해 주는 함수인데, array는 int형 데이터가 7개 있으므로 sizeof(array) 는 4 * 7 = 28, 즉 28이게 되며 sizeof(array[0]) 은 int형 데이터 한개이므로 4, 즉 28/4는 7. 즉 일곱개의 데이터가 있음을 알 수 있습니다. 배열은 0번방 부터 시작하므로 R이 있어야할 자리는 array의 6번째 방. 그래서 1을 뺐습니다.

L은 pivot보다 큰 수를 찾을때까지, R은 pivot보다 작은 수를 찾을때까지 이동합니다.

5 - 3 - 7 - 6 - 2 - 1 - 4 
p       L               R

5 - 3 - 4 - 6 - 2 - 1 - 7 
p       L               R

while(true)
    {
        while(p[L] < pivot)
            L++;
 
        while(p[R] > pivot)
            R--;
 
        if(L > R)
            break;
 
        std::swap(p[L],p[R]);
        L++,R--;
    }
    std::swap(p[0], p[R]);

찾아서 array[L]과 array[R]을 서로 맞바꿉니다. 그리고 바꾼 방에는 이제 관심이 없으므로 L은 1증가 R은 1감소 합니다.

5 - 3 - 4 - 6 - 2 - 1 - 7 
p           L       R      

5 - 3 - 4 - 1 - 2 - 6 - 7 
p           L       R      

1과 6을 다시 바꿔주고 L은 증가 R은 감소. 그럼 두개의 값이 겹치죠? 2가 있는 4번방. 즉 L과 R의 값이 4가 됩니다.

2의 값이 pivot인 5의 값보다 작으니 L은 1증가, R은 그대로, if문에 의해서 L이 R보다 큰 지금과 같은 상황에 반복문이 종료되고

피벗과 R의 자리를 바꾸어 줍니다. pivot이 중간으로 가게 되죠.

2 - 3 - 4 - 1 - 5 - 6 - 7 
                p      

    return R;

void quickSortWrapper(int *p, int size)
{
    if(size <= 1)
        return;
 
    int pivot = partition(p,size);
 
    quickSortWrapper(p, pivot);
    quickSortWrapper(p+pivot+1,size-pivot-1);
}

위의 partition 함수를 이용하여 pivot을 구하고, 재귀적으로 정렬하는 퀵소트 wrapper 함수, 이름은 그냥 quickSort라고 써도 무방. partition함수와 마찬가지로 데이터 배열과 사이즈를 입력받음.

참고하시어 공부에 도움이 되었으면 좋겠습니다. 모르는 것은 댓글로 질문 달아주시면 보통 하루 이내로 답변 드립니다. 도움이 되었다면 하트모양 좋아요나 광고를 한번씩 눌러주세요! 큰 도움이 됩니다.