개념

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

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

Python

Cache사용

좀 더 직관적이다.

import random

def quick(a):
    if len(a) <= 1:
        return a

    pivot = a[len(a) // 2]
    less = []
    more = []
    equal = []
    for i in a:
        if i < pivot:
            less.append(i)
        elif i > pivot:
            more.append(i)
        else:
            equal.append(i)
    return quick(less) + equal + quick(more)

n = 20
a = [random.randrange(0, 40) for _ in range(n)]
print(" < origin >")
print(*a)

a = quick(a)

print("\\n< Quick (Cache) Sort >")
print(*a)

Cache 사용 안함

import random

def quick(a, start, end):
    if start >= end:
        return
    pivot = a[start]
    left = start + 1
    right = end
    done = False
    while not done:
        while left <= right and a[left] <= pivot:
            left += 1
        while left <= right and pivot <= a[right]:
            right -= 1
        if right < left:
            done = True
        else:
            a[left], a[right] = a[right], a[left]
    a[start], a[right] = a[right], a[start]
    quick(a, start, right-1)
    quick(a, right+1, end)

n = 20
a = [random.randrange(0, 50) for _ in range(n)]
print(" < origin >")
print(*a)

quick(a, 0, n-1)

print("\\n< Quick Sort >")
print(*a)

C

Generalized

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

#define BASE(base, idx) (char*)base + (idx)*width

void mem_swap(void* a, void* b, int width) {
    void* temp = malloc(width);
    memcpy(temp, b, width);
    memcpy(b, a, width);
    memcpy(a, temp, width);
}

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

void quick_sort(void* base, int start, int end, int width,
                int (*fcmp)(const void*, const void*)) {
    if (start >= end)
        return;
    void* pivot = BASE(base, start);
    int left = start + 1;
    int right = end;
    while (1) {
        while (left <= right && fcmp(BASE(base, left), pivot) <= 0)
            left++;

        while (left <= right && fcmp(BASE(base, right), pivot) >= 0)
            right--;
        if (right < left) break;
        mem_swap(BASE(base, left), BASE(base, right), width);
    }
    mem_swap(BASE(base, right), pivot, width);

    quick_sort(base, start, right - 1, width, fcmp);
    quick_sort(base, right + 1, end, width, fcmp);
}

int main() {
    srand((unsigned int)time(NULL));

    int i, n = 20;
    int* a = (int*)calloc(n, sizeof(int));
    for (i = 0; i < n; i++)
        a[i] = rand() % 50;

    printf("origin : \\n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);

    quick_sort(a, 0, n - 1, sizeof(int), cmp);

    printf("\\n\\nQuick sorted : \\n");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

C++

코드가 이해하기 어려울 수 있다. 대략적으로 설명하자면 j와 pivot을 비교해서 j가 pivot보다 작으면 i의 왼쪽으로 보내버린다. j가 진행되면서 i의 왼쪽은 pivot보다 작은것들만 오게 되고 pivot이 i+1과 자리를 바꾸게 된다.

#include <ctime>
#include <iostream>
#include <random>

using namespace std;

template <typename T>
void quick_sort(T* a, int start, int end) {
    if (start >= end) return;

    int i = start - 1, j = start;
    T& pivot = a[end];
    for (; j < end; j++) {
        if (a[j] < pivot)
            swap(a[++i], a[j]);
    }
    swap(a[++i], pivot);
    quick_sort(a, start, i - 1);
    quick_sort(a, i + 1, end);
}

int main() {
    mt19937 mt((unsigned int)time(nullptr));
    uniform_int_distribution<int> gen(0, 49);

    int n = 20;
    int* a = new int[20];
    for (int i = 0; i < n; i++) {
        a[i] = gen(mt);
    }
    cout << "origin : \\n";
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }

    quick_sort(a, 0, n - 1);
    cout << "\\n\\nQuick sort : \\n";
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
}