퀵 정렬(Quick Sort)

: 분할 정복 알고리즘
: 비교 정렬
: 불안정 정렬
: 시간 복잡도는 평균 O(n log2 n)

합병정렬과 같은 분할 정복 알고리즘
pivot(피벗)이라는 원소를 지정해서 기준으로 사용
피벗보다 작은 요소는 피벗의 왼쪽으로
피벗보다 큰 요소는 피벗의 오른쪽으로
이 상태로 피벗을 제외한 왼쪽과 오른쪽을 다시 정렬

일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

출처: 위키피디아

---

알고리즘 예시

5 7 3 1 4 9 8 6 2
총 9개의 숫자가 있다고 해보자

(5) 7 3 1 4 9 8 6 2
5를 피벗으로 설정

low와 high가 피벗보다 크고 피벗보다 작은 요소를 찾으면 멈추고 교환

(5) 2 3 1 4 9 8 6 7
7(low)와 2(high)를 교환

4 2 3 1 (5) 9 8 6 7
4(low)와 9(high)인 상태에서
low와 pivot을 교환해 5(pivot) 자리 확정

(4) 2 3 1 (5) 9 8 6 (7)
이전 피벗 5의 왼쪽과 오른쪽을 다시 정렬
새로운 피벗 4 설정
새로운 피벗 7 설정

...

이렇게
한 번 정렬을 할 때마다 한 자리는 확정됨 (피벗)

---

특징

• 분할 정복 알고리즘
  그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘

• 비교 정렬
  원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘
  비교 정렬이 아닌 것은 counting sort, radix sort 같은 것

• 불안정 정렬
  동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식
  예를 들어서 b B c a 가 있다고 하면
  퀵 정렬시 a B b c 가 될 수 있음
  (pivot이 맨 오른쪽 값이라고 한다면)

• 시간 복잡도는 평균 O(n log2 n)
  리스트 분할이 항상 리스트의 가운데에서 이루어진다면
  (log2 n)개의 패스와 평균 n번의 비교가 이루어져야되므로
  O(n log2 n)
  하지만 최악의 경우 (계속 불균형하게 리스트가 나누어지는 경우)
  시간 복잡도는 거의 O(n^2)

---

소스코드 (C)

#include <stdio.h>
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[10];
int n;

int partition(int list[], int left, int right)
{
    int pivot, temp;
    int low, high;

    low = left;
    high = right + 1;
    //pivot을 맨 왼쪽 요소로
    pivot = list[left];

    do
    {
        do
            low++;
        while (list[low] < pivot);
        do
            high--;
        while (list[high] > pivot);
        if (low < high) SWAP (list[low], list[high], temp);
    } while (low < high);

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

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

소스코드 (C++)

#include <iostream>

using namespace std;

int arr[1000001];

void quick_sort(int left, int right)
{
    if(left >= right)
        return ;

    int pivot, low, high;
    //배열의 중앙부분을 pivot으로
    pivot = arr[(left + right) / 2];
    low = left;
    high = right;

    while (low <= high)
    {
        while (arr[low] < pivot)
            low++;
        while (arr[high] > pivot)
            high++;
        if (low <= high)
        {
            swap(arr[low], arr[high]);
            low++;
            high++;
        }
    }
    quick_sort(left, high);
    quick_sort(low, right);
}

---

참고

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

C언어로 쉽게 풀어쓴 자료구조