Quick Sort (퀵 정렬)

알고리즘

퀵 정렬의 기본 아이디어는, 

기준이 되는 숫자를 정해서 그것보다 큰 원소들과 작은 원소들로 편을 갈라놓고 정렬하자는 것이다.

이 아이디어를 따라가기 위해서는 기준이 되는 숫자를 어떻게 정할 것인가,

그리고 큰 원소들과 작은 원소들을 어떻게 분리해 둘 것인가 하는 것이 주요 목표가 될 것이다.

백마디 설명 보다는 역시 예제를 하나 꺼내는 것이 좀 더 설명하기 쉬울 것 같다.

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

기준이 되는 숫자를 Pivot 이라고 부르는데,

맨 앞에 있는 숫자를 Pivot으로 삼을수도 있고, 정 가운데 있는 숫자를 Pivot으로 삼을 수도 있다.

사실 어떤 숫자를 Pivot으로 하든 상관이 없다.

이 예제에서는 임의로 정 가운데(?) 있는 33이라는 숫자를 택해보겠다.

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

우리는 양쪽 끝에서부터 각각의 원소를 하나하나 확인할 것이다.

왼쪽에서 접근하는 인덱스를 i,

오른쪽에서 접근하는 인덱스를 j라고 하자.

왼쪽에서 접근하는 인덱스는 33 보다 크거나 같은 경우에 멈추고,

오른쪽에서 접근하는 인덱스는 33 보다 작거나 같은 경우에 멈춘다.

그렇다면 i는 시작하자마자 45에서 멈추고, j는 11에서 멈추게 된다.

이렇게 되는 경우 두개의 원소를 맞교환한다.

11, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 45, 43

계속 접근을 하다 보면, 아래와 같이 교환이 계속 된다.

11, 28, 98, 15, 52, 44, 33, 39, 40, 38, 77, 68, 45, 43

11, 28, 33, 15, 52, 44, 98, 39, 40, 38, 77, 68, 45, 43

계속 접근을 하다보면 i는 52에서 멈출 것이고 j는 15에 도착하게 되는데,

i보다 j가 작아지는 경우에는

j가 있는 위치와 Pivot의 숫자를 맞교환 해준다.

즉, 위의 예제에서는 15와 33을 맞교환한다.

11, 28, 15, 33, 52, 44, 98, 39, 40, 38, 77, 68, 45, 43

이렇게 하면 Pivot 인 33의 왼쪽 편에는 33보다 작거나 같은 숫자, 

오른 편에는 33보다 크거나 같은 숫자가 위치하게 된다.

이렇게 해서 생긴 두개의 편에서 각각 다시 Quick Sort를 한다.

이렇게 계속 해서 정렬하면서, 정렬하려는 원소가 한 개가 될 때까지 정렬하면 정렬이 완료되는 방식이다.

* 수정된 내용
다만 pivot은 정렬대상에서 제외되어야 하는데,
pivot을 중간에서 설정하는 경우에는 이 점에 대해서 고려해야 하므로 추가적인 코드가 필요하다.
따라서 아래에는 맨 첫번째 원소를 pivot으로 설정한뒤, 나머지 뒷 부분의 array들을 정렬하고,
pivot과 j를 맞교환 함으로써 sorting을 마친다. 

코드

#include <stdio.h>
#define LEN 9

void quick_sort(int num[],int start, int end);
void tracer(int num[],int len);

int main(void){    
    int testArr[] = {485,241,454,325,452,685,498,890,281};
    quick_sort(testArr, 0, LEN-1); // 퀵 정렬 함수 호출
}

void quick_sort(int num[],int start, int end){
    int i,j,p;
    int tempValue; // 스왑 임시 저장소
    if (start < end) {
        i = start+1; // 양끝에서 접근할 값 정의
        j = end;
        p = num[start]; // pivot을 맨 처음 값으로 설정
        do {
            while (num[i] < p){
                i++; // pivot보다 크거나 같은 값 만날 때까지
            };
            while (num[j] > p) {
                j--; // pivot보다 작거나 같은 값 만날 때까지
            }
            // 구한 i, j 인덱스의 값을 서로 스왑
            if (i < j){
                tempValue = num[j];
                num[j] = num[i];
                num[i] = tempValue;
            }
        } while (i < j); // i보다 j가 클때만 동작
        num[start] = num[j];
        num[j] = p;
        printf("[start Index: %d, end Index: %d, Pivot: %d]\n",start,end,p);
        // pivot값 프린트
        tracer(num,LEN); // Array 전체 프린트
        quick_sort(num,start,j-1); // 왼쪽 편 같은 방법으로 sorting
        quick_sort(num,j+1,end); // 오른쪽 편 같은 방법으로 sorting
    }
}


void tracer(int num[],int len){
    int i;
    for(i=0;i<len;i++){
        printf("%d\t",num[i]);
    }
    printf("\n\n");
}

결과

분석

첫번째 줄에서 첫번째 숫자인 485가 Pivot이 되며, 

왼편에는 485보다 작거나 같은 숫자, 오른편에는 485보다 크거나 같은 숫자가 위치한다.

두번째 경우에는 왼편의 5개 숫자에 대해서만 퀵 정렬을 시작하게 되고,

Pivot을 281로 설정하고, 마찬가지로 정렬을 한다.

나머지 경우에 대해서도 마찬가지로 정렬을 수행하면, 최종적으로 오름차순 정렬이 끝나게 된다.