[알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬은 가장 빠른 정렬 알고리즘 중 하나로 널리 사용되고 있다. 

먼저 전체에서 데이터값 하나(A)를 선택한다. 그리고 A를 기준으로 A보다 큰 그룹과 작은 그룹으로 나눈다. 이때 A(그룹을 나누는 기준)를 피벗(pivot)이라고 한다. 퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마친다.
ps. 피벗은 마음대로 선택할 수 있고, 피벗은 왼쪽 그룹과 오른쪽 그룹 어디에 들어가도 상관없다.

 

코드

 // 퀵 정렬 함수
 void quick (int a[], int left, int right) {
     int pl = left; // 왼쪽 커서
     int pr = right; // 오른쪽 커서
     int x = a[(pl + pr) / 2]; // 피벗은 가운데 요소로 선택
     
     do {
         while(a[pl] < x) pl++;
         while(a[pr] > x) pr--;
         if(pl <= pr) {
             swap(int, a[pl], a[pr]);
             pl++;
             pr--;
         }
     } while(pl <= pr);
     if(left < pr) quick(a, left, pr);
     if(pl < right) quick(a, pl, right);
 }

퀵 정렬의 시간복잡도 : O(n log n)

(피벗의 선택 방법에 따라 시간 복잡도가 증가할 수도 있다-> 매번 최악의 피벗선택의 경우 O(n^2))

퀵 정렬은 서로 이웃하지 않고 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않다.

 

 

퀵 정렬 개선 - 1
퀵 정렬은 요소의 개수가 적은 배열에 대해서는 처리가 아주 빠르게 진행되지는 않는다.
요소 개수가 9개 이하인 그룹은 단순 삽입 정렬로 동작하는 함수로 수정하면 좋다.

 

코드

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

//-- 단순 삽입 정렬
void insertion(int a[], int n)
{
    int i, j;

    for (i = 1; i < n; i++) {
        int tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

// 퀵 정렬 (요솟수가 9개 이하면 단순 삽입 정렬로 전환 : 재귀 버전)
void quick(int a[], int left, int right)
{
    if (right - left < 9)
        insertion(&a[left], right - left + 1);
    else {
        int pl = left;
        int pr = right;
        int x = a[(pl + pr) / 2];

        do {
            while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr) {
                swap(int, a[pl], a[pr]);
                pl++;
                pr--;
            }
        } while (pl <= pr);

        if (pr - left < right - pl) {
            swap(int, pl, left);
            swap(int, pr, right);
        }
        if (left < pr)  quick(a, left, pr);
        if (pl < right) quick(a, pl, right);
    }
}

 

퀵 정렬 개선 - 2
피벗 선택 방법은 퀵 정렬의 실행 효율에 큰 영향을 준다.
나눌 배열의 요소 개수가 3 이상이면 임의로 3 요소를 선택하고 그중에서 중앙값인 요소를 피벗으로 선택하는 방법
이렇게하면 피벗 선정의 최악의 경우는 피할 수 있다.

 

코드 (처음 중간 끝 요소 선택, + 개선 1 방법을 토대로 작성)

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

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

//--- a, b, c 중 가운데 값을 구합니다.
int med3(int a, int b, int c)
{
    if (a >= b)
        if (b >= c)
            return b;
        else if (a <= c)
            return a;
        else
            return c;
    else if (a > c)
        return a;
    else if (b > c)
        return c;
    else
        return b;
}

//--- 단순 삽입 정렬
void insertion(int a[], int n)
{
    int i, j;

    for (i = 1; i < n; i++) {
        int tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

void quick(int a[], int left, int right)
{
    if (right - left < 9)
        insertion(&a[left], right - left + 1);
    else {
        int pl = left;
        int pr = right;
        int x = med3(a[pl], a[(pl + pr) / 2], a[pr]);

        do {
            while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr) {
                swap(int, a[pl], a[pr]);
                pl++;
                pr--;
            }
        } while (pl <= pr);

        if (pr - left < right - pl) {
            swap(int, pl, left);
            swap(int, pr, right);
        }
        if (left < pr)  quick(a, left, pr);
        if (pl < right) quick(a, pl, right);
    }
}

 

퀵 정렬 개선 - 3
피벗 선택 방법은 퀵 정렬의 실행 효율에 큰 영향을 준다.
나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소를 교환한다. 피벗으로 끝에서 두 번째 요소의 값을 선택하여 나눌 대상의 범위를 a[left+1] ~ a[right - 2]로 좁힌다.
이 방법은 나눌 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 떄 스캔할 요소를 3개씩 줄일 수 있다는 장점이 있다.

 

코드 ( + 개선 1 방법을 토대로 작성)

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

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

int sort3elem(int x[], int a, int b, int c)
{
    if (x[b] < x[a]) swap(int, x[b], x[a]);
    if (x[c] < x[b]) swap(int, x[c], x[b]);
    if (x[b] < x[a]) swap(int, x[b], x[a]);
    return b;
}

void insertion(int a[], int n)
{
    int i, j;

    for (i = 1; i < n; i++) {
        int tmp = a[i];
        for (j = i; j > 0 && a[j - 1] > tmp; j--)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

void quick(int a[], int left, int right)
{
    if (right - left < 9)
        insertion(&a[left], right - left + 1);
    else {
        int pl = left;
        int pr = right;
        int x;
        int m = sort3elem(a, pl, (pl + pr) / 2, pr);
        x = a[m];
        swap(int, a[m], a[right - 1]);
        pl++;
        pr -= 2;

        do {
            while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr) {
                swap(int, a[pl], a[pr]);
                pl++;
                pr--;
            }
        } while (pl <= pr);

        if (pr - left < right - pl) {
            swap(int, pl, left);
            swap(int, pr, right);
        }
        if (left < pr)  quick(a, left, pr);
        if (pl < right) quick(a, pl, right);
    }
}

 

비재귀적인 퀵 정렬 구현

코드

 //퀵 정렬을 비재귀적으로 구현한 프로그램
 void quick (int a[], int left, int right) {
     IntStack lstack;
     IntStack rstack;
     
     Initialize(&lstack, right-left+1);
     Initialize(&rstack, right-left+1);
     
     Push(&lstack, left);
     Push(&rstack, right);
     
     
     while(!IsEmpty(&lstack)) { // lstack, rstack 둘다 함께 비고 채워지므로 둘중 아무거나 하나로만 체크함
         
         int pl = (Pop(&lstack, &left), left); //lstack에서 팝한 값을 left에 대입한 다음 그 left의 값을 다시 pl에 대입
         int pr = (Pop(&rstack, &right), right); //rstack에서 팝한 값을 right에 대입한 다음 그 right의 값을 다시 pr에 대입
         
         int x = a[(left + right) / 2]; // 피벗은 가운데 요소로 선택
         
         //과정 출력해보면 알다시피, 재귀적으로 했을떄와 다르게 뒷 그룹 문저 처리가된다. 이는 아래 if문의 Push 순서와 연관이있다.
         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] < x) pl++;
             while(a[pr] > x) pr--;
             if(pl <= pr) {
                 swap(int, a[pl], a[pr]);
                 pl++;
                 pr--;
             }
         } while(pl <= pr);
         
         // 순서가 현재 재귀구현때와 동일한데, 이렇게되면 둘다 참일 때 앞 그룹이 아닌 뒷 그룹부터 처리가 진행된다. 처리 순서가 바뀌는 것일 뿐 결과에는 문제가없으며 바꿔주고싶다면 if순서를 바꿔주면 되겠다.
         if(left < pr) {
             Push(&lstack, left);
             Push(&rstack, pr);
         }
         if(pl < right) {
             Push(&lstack, pl);
             Push(&rstack, right);
         }
     }
     Terminate(&lstack);
     Terminate(&rstack);
 }

비재귀적인 퀵 정렬 개선 - 1
요소의 개수가 많은 그룹을 먼저 푸시하면 스택의 실 사용 용량을 log n개 이하로 줄일 수 있다.

 

코드

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

#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)

//--- 퀵 정렬 (요솟수가 작은 그룹을 먼저 분할 : 비재귀 버전)
void quick(int a[], int left, int right)
{
    IntStack lstack;
    IntStack rstack;

    Initialize(&lstack, right - left + 1);
    Initialize(&rstack, right - left + 1);

    Push(&lstack, left);
    Push(&rstack, right);

    while (!IsEmpty(&lstack)) {
        int pl = (Pop(&lstack, &left), left);
        int pr = (Pop(&rstack, &right), right);
        int x = a[(left + right) / 2];

        do {
            while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr) {
                swap(int, a[pl], a[pr]);
                pl++;
                pr--;
            }
        } while (pl <= pr);

        if (pr - left < right - pl) {
            swap(int, pl, left);
            swap(int, pr, right);
        }
        if (left < pr) {
            Push(&lstack, left);
            Push(&rstack, pr);
        }
        if (pl < right) {
            Push(&lstack, pl);
            Push(&rstack, right);
        }
    }
}