Quick Sort(퀵 정렬)

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작합니다.

퀵 정렬은 피벗(pivot)이 사용됩니다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗(pivot)이라고 합니다.

 

퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 합니다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵 정렬을 구분합니다.

 

아래 사진처럼 데이터가 있습니다.

피벗을 서정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾습니다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해줍니다. 이러한 과정을 반복하면 '피벗'에 대하여 정렬이 수행됩니다.

 

Step 1)

리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 '5'이고, 이후에 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택됩니다. 이 두데이터의 위치를 서로 변경합니다.

Step 2)

그 다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾고, 찾은 뒤에는 두 값의 위치를 서로 변경합니다.현재 '9'와 '2'가 선택되었으므로 이 두 데이터의 위치를 서로 변경합니다.

Step 3)

다시 피벗보다 큰 데이터와 작은 데이터를 찾습니다. 단, 현재 왼쪽에서부터 찾은 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 것을 알 수 있습니다. 이렇게 두 값이 엇갈린 경우에는 '작은 데이터'와 '피벗'의 위치를 서로 변경합니다.즉, 작은 데이터인 '1'과 피벗인 '5'의 위치를 서로 변경하여 분할을 수행합니다.

 

Step 4 - 1단계 분할 완료)

아래 사진처럼 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 보면 '5'의 왼쪽에 있는 데이터는 모두 '5'보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있습니다.

이러한 작업과정을 분할(Divide) 또는 파티션(Partition)이라고 합니다.

이러한 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬한다면 왼쪽 리스트는 어떻게 정렬되어도 모든 데이터가 '5'보다 작고, 마찬가지로 오른쪽 리스트도 어떻게 정렬되든 모든데이터가 '5'보다 큽니다. 따라서 왼쪽 리스트와 오른쪽 리스트에도 각각 피벗을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어질 것입니다.

 

Step 5 - 왼쪽 리스트 정렬)

 

Step 6 - 오른쪽 리스트 정렬)

 

퀵 정렬에서는 이처럼 특정한 리스트에서 피벗을 설정하고 정렬을 한 후, 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행합니다. '재귀 함수'와 동작원리가 같고 퀵 정렬을 재귀 함수 형태로 만들 때 구현이 매우 간결해집니다. 

퀵 정렬의 종료 조건은 현재 리스트의 데이터 개수가 1개인 경우이며, 리스트의 원소가 1개라면 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능합니다.

 

 

#include <stdio.h>
 
#define MAX_LEN     10
 
void Swap(int *ap_value1, int *ap_value2)
{
    int temp = *ap_value1;
    *ap_value1 = *ap_value2;
    *ap_value2 = temp;
}
 
void QuickSort(int *arr, int start, int end) {
    if (start >= end) return; // 원소가 1개인 경우 종료
 
    int pivot = start; // 피벗은 첫 번째 원소
    int left = start + 1;
    int right = end;
 
    while (left <= right) {
        // 피벗보다 큰 데이터를 찾을 때까지 반복
        while (left <= end && arr[left] <= arr[pivot]) left++;
        // 피벗보다 작은 데이터를 찾을 때까지 반복
        while (right > start && arr[right] >= arr[pivot]) right--;
        // 엇갈렸다면 작은 데이터와 피벗을 교체
        if (left > right) Swap(&arr[pivot], &arr[right]);
        // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
        else Swap(&arr[left], &arr[right]);
    }
    // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    QuickSort(arr, start, right - 1);
    QuickSort(arr, right + 1, end);
}
 
int main(void) {
    int arr[MAX_LEN] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
 
    QuickSort(arr, 0, MAX_LEN - 1);
 
    for (int i = 0; i < MAX_LEN; i++) {
        printf("%d ", arr[i]);       
    }
}

 

시간 복잡도

선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도가 O(n^2)입니다. 

퀵 정렬의 평균 시간 복잡도는 O(NlogN)입니다.