퀵 정렬 (Quick Sorting)

퀵 정렬은 평균적으로 매우 빠른 수행 속도를 보인다.

이 역시 분할 정복 방법에 근거한다.

합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할한다.

각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용한다.

그러나 퀵 정렬은 리스트를 다음과 같은 방법으로 비균등하게 분할한다.

먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다.

여기서는 리스트의 첫 번째 요소라고 가정한다.

피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.

결과적으로 피벗을 중심으로 왼쪽은 작은 요소들, 오른쪽은 큰 요소들로 구성된다.

이 상태에서 피벗을 제외한 왼쪽, 오른쪽 리스트를 다시 정렬하면 전체 리스트가 정렬된다.

퀵 정렬 역시 합병 정렬과 마찬가지로 퀵 정렬 함수가 다시 부분 리스트에 대해 순환 호출된다.

부분 리스트에서도 다시 피벗을 정하고 이를 기준으로 2개의 부분 리스트로 나누는 과정이 되풀이된다.

이러한 과정을 부분 리스트들이 더 이상 분할이 불가능할 때까지 계속한다.

퀵 정렬의 외부적인 코드는 다음과 같다.

void quick_sort(int list[], int left, int right) {
    if (left < right) {
        int pivot = partition(list, left, right);
        quick_sort(list, left, pivot - 1); // 왼쪽 부분 리스트
        quick_sort(list, pivot + 1, right); // 오른쪽 부분 리스트
    }
}

2번 라인 - 정렬할 범위가 2개 이상의 데이터이면

3번 라인 - partition()를 호출하여 피벗을 기준으로 2개의 리스트로 분할한다. partition 함수의 반환 값은 피벗의 위치가 된다.

4번 라인 - 왼쪽 부분 리스트 정렬, (현재 left ~ 피벗-1) 까지를 대상으로 순환 호출 (피벗 제외)

5번 라인 - 오른쪽 부분 리스트 정렬, (피벗+1 ~ 현재 right) 까지를 대상으로 순환 호출 (피벗 제외)

퀵 정렬에서 가장 중요한 함수는 partition()이다. 데이터가 들어있는 배열 list의 left부터 right까지의 리스트를, 피벗을 기준으로 2개의 부분 리스트로 나누게 된다.

(5, 3, 8, 4, 9, 1, 6, 2, 7)이라는 리스트를 두개의 부분 리스트로 나눈 과정을 예로 들어본다.

간단히 하기 위해 피벗 값을 입력 리스트의 첫 번째 데이터로 한다.

따라서 피벗은 0번 인덱스인 5가 해당한다.

2개의 인덱스 변수 low, high를 사용한다.

low는 왼쪽 부분 리스트를 만드는데 사용하고, high는 오른쪽 부분 리스트를 만드는데 사용된다.

인덱스 변수 low는 왼쪽에서 오른쪽으로 탐색하다가 피벗보다 큰 데이터(8)를 찾으면 멈춘다.

인덱스 변수 high는 오른쪽에서 왼쪽으로 탐색하다가 피벗보다 작은 데이터(2)를 찾으면 멈춘다.

즉, 탐색이 멈추어진 위치는 각 부분 리스트에 적합하지 않은 데이터라는 의미가 된다.

(피벗보다 작은 데이터는 피벗보다 왼쪽에, 피벗보다 큰 데이터는 피벗보다 오른쪽에 있어야 하므로)

둘 다 멈추었다면 low와 high가 가리키는 두 데이터를 교환한다.

이러한 탑색-교환 과정은 low와 high가 엇갈릴 때까지 반복한다.

언젠가 low와 high가 엇갈린다면, 이제 더 이상 전체 리스트에 피벗과 비교할 숫자가 없다는 뜻이다.

그 순간의 high와 pivot의 데이터를 교환한다.

low가 아닌 high인 이유는 다음과 같다.

pivot은 맨 처음의 값(5)이고, low와 high는 각각 피벗을 기준으로 왼쪽과 오른쪽에 갈 숫자를 서로 교환하며 각 부분 리스트의 모든 인덱스를 한 번씩은 들른 상태이다.

엇갈린 순간,

현재 low의 위치는 피벗(5)보다 큰 값에 가 있을 것이고

현재 high의 위치는 피벗(5)보다 작은 값에 가 있을 것이다.

low와 바꾼다면 결국 피벗보다 큰 값이 맨 처음, 즉 피벗의 왼쪽으로 가기 때문에 로직 상 오류인 것이다.

따라서 pivot의 값을, low가 아닌 high와 바꿔야 한다

이로서 pivot은 리스트의 중간으로 오게 된다.

왼쪽은 pivot보다 작은 값들로 구성된 부분 리스트

오른쪽은 pivot보다 큰 값들로 구성된 부분 리스트이며 이러한 부분 리스트들은 아직 정렬되지 않았으므로 다시 정렬해야한다.

부분 리스트 역시도 Quick Sort로 정렬을 한다.

왼쪽 부분 리스트의 left는 상위 리스트의 left부터 시작, right는 상위 리스트의 pivot-1부터 시작한다.

오른쪽 부분 리스트의 left는 상위 리스트의 pivot+1부터 시작, right는 상위 리스트의 right부터 시작한다.

left는 부분 리스트의 시작, right는 부분 리스트의 끝이므로 left < right가 아니라면 이미 배열의 크기가 1인 경우이므로, 결국 left < right가 false가 될 때 까지 반복하면 모든 부분 리스트가 정렬이 되고 이는 곧 전체 리스트의 정렬이 완료됐다는 의미가 된다.

 - pivot을 맨 처음 인덱스로 지정하는 경우 -

 pivot : 현재 부분리스트에서 정렬하는데 필요한 기준이 되는 첫 번째 인덱스의 값. high와 low의 인덱스가 엇갈리면 high와 교환된다.

 

 left : 현재 부분리스트의 가장 왼쪽 인덱스(현재 부분리스트의 피벗의 인덱스)

 

 right : 현재 부분리스트의 가장 오른쪽 인덱스

 

 low : 피벗을 제외하고 left+1부터 시작되서 오른쪽으로 가는 인덱스. 이 값은 pivot보다 작아야 한다.

따라서 (low인덱스의 값 > pivot 값)의 경우, 해당 low인덱스의 값은 자신의 영역이 아니므로 멈추며, high가 멈춘 경우 low인덱스의 값과 high인덱스의 값을 교환

 

 high : right부터 시작되서 왼쪽으로 가는 인덱스. 이 값은 pivot보다 커야 한다.

 

따라서 (high인덱스의 값 < pivot 값)의 경우, 해당 high인덱스의 값은 자신의 영역이 아니므로 멈춘 후 low인덱스의 값과 high인덱스의 값을 교환. high와 low의 인덱스가 엇갈리면 pivot과 교환된다.

 

위와 같은 로직을 코드로 표현하면 다음과 같다.

int partition(int list[], int left, int right) {
    int pivot, tmp;
    int low, high;
    low = left;
    high = right + 1;
    pivot = list[left];

    do {
        do low++;  while (low <= right && list[low] < pivot);
        do high--; while (high >= left && list[high] > pivot);
        if (low < high) SWAP(list[low], list[high], tmp);
    } while (low < high);

    SWAP(list[left], list[high], tmp);
    return high;
}

4번 라인 - low는 left+1에서 출발, do-while에서 먼저 증가시키고 시작한다.

5번 라인 - high는 right에서 출발, do-while에서 먼저 감소시키고 시작한다.

6번 라인 - 정렬할 리스트의 가장 왼쪽 데이터를 pivot으로 선택

8번 라인 - low와 high가 교차할 때까지 계속 반복.

9번 라인 - list[low]가 pivot보다 작으면 계속 low를 증가

10번 라인 - list[high]가 pivot보다 크면 계속 high를 증가

11번 라인 - low와 high가 아직 교차하지 않았으면 list[low]와 list[high]를 교환

12번 라인 - 만약 low와 high가 교차하였으면 반복을 종료

14번 라인 - list[left]와 list[high]를 교환

15번 라인 - pivot의 위치은 high를 반환

전체 프로그램

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 10
#define SWAP(x, y, t) (t=x, x=y, y=t)

int partition(int list[], int left, int right) {
    int pivot, tmp;
    int low, high;
    low = left;
    high = right + 1;
    pivot = list[left];
    
    do {
        do low++;  while (low <= right && list[low] < pivot);
        do high--; while (high >= left && list[high] > pivot);
        if (low < high) SWAP(list[low], list[high], tmp);
    } while (low < high);
    
    SWAP(list[left], list[high], tmp);
    return high;
}

void quick_sort(int list[], int left, int right) {
    if (left < right) {
        int q = partition(list, left, right);
        quick_sort(list, left, q - 1);
        quick_sort(list, q + 1, right);
    }
}

void main() {
    int list[MAX_SIZE];
    
    printf("<버블정렬>\n정렬 이전 배열 : ");
    for (int i = 0; i < MAX_SIZE; i++) {
        list[i] = rand() % MAX_SIZE;
        printf("%d ", list[i]);
    }
    printf("\n");
    
    quick_sort(list, 0, MAX_SIZE-1); // 퀵 정렬 호출
    
    printf("최종 정렬 결과 : ");
    for (int i = 0; i < MAX_SIZE; i++)
        printf("%d ", list[i]);
    printf("\n");
    system("pause");

}

각 스캔과정은 생략한다.

<성능평가>

4만개의 크기를 주고 시간을 재는 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 40000
#define SWAP(x, y, t) (t=x, x=y, y=t)

int partition(int list[], int left, int right) {
    int pivot, tmp;
    int low, high;
    low = left;
    high = right + 1;
    pivot = list[left];
    
    do {
        do low++;  while (low <= right && list[low] < pivot);
        do high--; while (high >= left && list[high] > pivot);
        if (low < high) SWAP(list[low], list[high], tmp);
    } while (low < high);
    
    SWAP(list[left], list[high], tmp);
    return high;
}

void quick_sort(int list[], int left, int right) {
    if (left < right) {
        int q = partition(list, left, right);
        quick_sort(list, left, q - 1);
        quick_sort(list, q + 1, right);
    }
}

void main() {
    int list[MAX_SIZE];
    
    for (int i = 0; i < MAX_SIZE; i++)
        list[i] = rand() % MAX_SIZE;
    
    clock_t start = clock(); // 시간재기 시작
    quick_sort(list, 0, MAX_SIZE-1); // 퀵 정렬 호출
    clock_t end = clock(); // 시간재기 끝
    
    double diff = (double)(end - start) / 1000;
    printf("퀵 정렬\n크기 : 40000개\n%.4lf초\n", diff);
    system("pause");

}

 

n이 2의 거듭제곱이라고 가정하고, 만약 퀵 정렬에서의 리스트 분할이 항상 리스트의 가운데에서 이루어진다고 가정하면 합병 정렬의 복잡도 분석과 마찬가지로 n개의 레코드를 가지는 리스트는 ​의 크기로 나누어질 것이다.

​

크기가 1이 될 때까지 나누어지므로 일 때까지 나누어질 것이고, 따라서 개의 패스가 필요하다.

​

각각의 패스에서는 전체 리스트의 대부분이 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어지므로 퀵 정렬은 비교 연산을 총 ​번 실행하게 되어 의 복잡도를 가지는 알고리즘이 된다.

여기서 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

퀵 정렬에서의 최악의 경우는 리스트가 계속 불균형하게 나누어지는 경우이다.

예를 들어 이미 정렬된 리스트에 대해 퀵 정렬을 실행하는 경우에 해당한다.

(1 2 3 4 5 6 7 8 9)

1 (2 3 4 5 6 7 8 9)

1 2 (3 4 5 6 7 8 9)

...

1 2 3 4 5 6 7 8 9

이 경우 레코드의 수 만큼 총 n번의 패스가 실행되고, 각 패스에서 n번의 비교가 이루어지게 되므로 비교 연산을 번 실행하게 된다.

즉, 퀵 정렬은 최악의 경우 으로 나타난다. 특히 의 복잡도를 가지는 다른 정렬 알고리즘과 비교하였을 때도 가장 빠르다.

이는 퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 자신의 자리로 가게 됨으로써 추후 연산에서 제외되는 특성 때문이다.

퀵 정렬은 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는 등의 장점이 있는 반면, 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸리는 등의 단점도 있다.

이러한 불균형 분할을 방지하기 위해 피벗 선택 시 단순히 왼쪽 데이터를 사용하는 대신 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택하곤 한다.

많이 사용되는 방법은 리스트 내의 몇 개의 데이터 중 크기 순으로 중간 값(median)을 피벗으로 선택하는 것이다.

일반적으로 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기순으로 중간 값을 선택하는 방법(median of three)이 많이 사용된다.