[Algorithm] C - 퀵 정렬(Quick Sort)

요약

시간 복잡도 : O(n log n) ~ O(n ^ 2)

• 정렬할 데이터에서 피벗을 기준으로 두 개의 비균등한 크기로 분할하는 작업을 반복
• 피벗 이하의 그룹과 이상의 그룹이 왼쪽, 오른쪽으로 분리되었을 경우 배열을 다시 분할
• 요소가 1개가 되었을 때 분할을 멈춤

퀵 정렬(Quick Sort)

퀵 정렬이란 정렬할 데이터에서 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬하는 알고리증믈 말한다.
퀵 정렬은 가장 빠른 정렬 알고리즘으로, 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 붙인 이름으로,
속도가 빠른 만큼 많이 사용되는 정렬 알고리즘이다.

만약 어떤 학생 그룹이 있고, 수가 8명이며 키 순서대로 정렬해야 되는 구조가 있다.
먼저 임의의 학생 A를 기준으로 두고, 그 학생의 키를 선택한다. 이때 이 학생의 키가 피벗이 된다.
피벗은 그룹을 나누는 기준으로 볼 수 있다.

이제 A 학생의 기준으로 큰 키와 작은 키의 그룹으로 나누고, 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복한다.
이러한 동작을 반복하여 최종적으로 모든 그룹이 1명이 되면 정렬을 마친다.

배열을 두 그룹으로 나누기

먼저 배열을 두 그룹으로 나눠야 한다.
어떤 배열이 있을 때 중간 값(임의의 값)을 피벗으로 선택하고, 피벗을 x, 왼쪽 끝 요소의 인덱스 pl,

오른쪽 끝 인덱스 pr로 선택한다.

그룹을 나누기 위해서 먼저 피벗 이하의 요소를 배열 왼쪽으로, 이상의 요소를 오른쪽으로 옮겨야 한다.
그러기 위해 2가지의 작업을 먼저 수행한다.

1. pl >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 옮김
2. pr <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 옮김

이 과정을 거치면 pl과 pr은 아래 그림의 위치에서 멈추게 된다.
pl이 위치한 지점은 피벗 값(6) 이상의 요소(7)가 있는 지점이고,
pr이 위치한 지점은 피벗 값(6) 이하의 요소(3)가 있는 지점이다.

여기서 왼쪽(pl)과 오른쪽(pr) 커서가 가리키는 요소 pl과 pr의 값을 교환한다.
그러면 피벗 이하의 값은 왼쪽으로 이동하고, 피벗 이상의 값은 오른 쪽으로 이동한다.

그 후 다시 작업을 진행하면 요소의 위치는 아래 그림과 같이 되고, 다시 값을 교환한다.

다시 작업을 진행하면 pl과 pr의 커서가 교차하여 변할 때가 오면 피벗 이상과 이하의 그룹으로 나뉜다.

이 과정이 되면 배열은 아래 처럼 나뉜다.

피벗 이하의 그룹 : a[0] ~ a[pl - 1]
피벗 이상의 그룹 : a[pr +1] ~ a[n - 1]

또한 그룹을 나누는 작업이 끝난 다음 pl > pr + 1인 경우에는 다음과 같은 그룹이 생길 수 있다.

피벗과 일치하는 값을 가지는 그룹 : a[pr + 1], ~ a[pl - 1]

아래 그림은 피벗과 일치하는 값을 가지는 그룹이 만들어지는 과정이다.

나눈 그룹을 또 두 그룹으로 나누기

피벗을 기준으로 두 그룹을 나눴다면, 나눈 그룹을 또 피벗을 설정해 그룹으로 나누어야 퀵 정렬이 완성된다.

위 그림과 같이 피벗을 기준으로 그룹을 나누는 일련의 과정들이 반복된다.
과정이 반복되다가 요소의 개수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없으므로, 요소의 개수가 2개 이상인 그룹만 나눈다.
즉, 최종적으로 2가지의 작업을 반복한다.

1. pr이 [0]보다 오른쪽에 있으면 (left < pr) 왼쪽 그룹을 나눈다.
2. pl이 [8]보다 왼쪽에 있으면 (pl < right) 오른쪽 그룹을 나눈다.

시간 복잡도

퀵 정렬은 배열을 나누어 정렬하는 과정을 반복하므로 시간 복잡도는 O(n log n)이다.
근데 매번 단 하나의 요소와 나머지 요소로 나누어 지려면 n 번의 분할이 필요하다.
이 경우 최악의 시간 복잡도로 O(n ^ 2)가 된다.

예제 코드

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

void QuickSort(int *a, int left, int right);
void Swap(int* num1, int* num2);

int main() 
{
    int i, n;
    int *x;
    
    printf("요소 개수 : ");
    scanf("%d", &n);
    
    x = malloc(sizeof(int) * n);
    
    for(i = 0; i < n; i++) {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }
    
    QuickSort(x, 0, n - 1);
    
    printf("오름차순 정렬\n");
    
    for(i = 0; i < n; i++) {
        printf("x[%d] = %d\n", i, x[i]);
    }
    
    free(x);

    return 0;
}

void Swap(int* num1, int* num2) 
{  
    int temp;
    
    temp = *num2;
    *num2 = *num1;
    *num1 = temp;
}

void QuickSort(int *a, int left, int right)
{
    // 배열의 왼쪽 커서 (이하 그룹)
    int pl = left;
    
    // 배열의 오른쪽 커서 (이상 그룹)
    int pr = right;
    
    // 배열의 중앙 값을 피벗으로 설정
    int pivot = a[(pl + pr) / 2];
    
    int i;
    
    // 분할 과정 출력
    printf("a[%d] ~ a[%d] : {", left, right);
    for(i = left; i < right; i++) {
        printf("%d, ", a[i]);
    }
    printf("%d}\n", a[right]);
    
    
    do {
        // 왼쪽 커서가 중앙을 넘어갔을 때(이하 -> 이상 교차)
        while(a[pl] < pivot) {
            pl++;
        }
        // 오른쪽 커서가 중앙을 넘어갔을 때 (이상 >- 이하 교차)
        while(a[pr] > pivot) {
            pr--;
        }
        
        // 이하 그룹과 이상 그룹이 교차했을 경우 값 교환
        if(pl <= pr) {
            Swap(&a[pl], &a[pr]);
            pl++;
            pr--;
        }
        
        // 피벗의 이상 이하 그룹 정렬
    } while(pl <= pr);
    
    if(left < pr) {
        QuickSort(a, left, pr);
    }
    if(pl < right) {
        QuickSort(a, pl, right);
    }
}

실행 결과

요소 개수 : 9
x[0] : 5
x[1] : 8
x[2] : 4
x[3] : 2
x[4] : 6
x[5] : 1
x[6] : 3
x[7] : 9
x[8] : 7
a[0] ~ a[8] : {5, 8, 4, 2, 6, 1, 3, 9, 7}
a[0] ~ a[4] : {5, 3, 4, 2, 1}
a[0] ~ a[2] : {1, 3, 2}
a[0] ~ a[1] : {1, 2}
a[3] ~ a[4] : {4, 5}
a[5] ~ a[8] : {6, 8, 9, 7}
a[5] ~ a[6] : {6, 7}
a[7] ~ a[8] : {9, 8}
오름차순 정렬
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 5
x[5] = 6
x[6] = 7
x[7] = 8
x[8] = 9

https://github.com/JeHeeYu/Algorithm/tree/main/Sort/Quick%20Sort

GitHub - JeHeeYu/Algorithm: 알고리즘 개념 및 문제 풀이

 

 

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편