2020-01-31

Quick sort

퀵 정렬은 평균적으로 가장 빠르고, 이해하기도 쉬운 정렬 알고리즘이다. 이 알고리즘의 핵심 알고리즘은 partition 이다. 흔히 pivot 이라고 부르는 메소드다. partition algorithm 은 Lumuto, hoare 두개의 방법이 존재한다. 최악의 경우에서 hoare 가 더 좋은 성능을 가진다.

하지만, hoare 는 구현하기 굉장히 까다롭다. 막상 구현해보면 쉽게 코드를 완성하는 경우가 거의 없다. 반면, lumuto 는 쉽게 완성 시킬 수 있다. 프로그래머는 언제나 유지보수 하기 좋은 코드를 선택해야 한다. 그래서 나는 Lumuto 를 partition 을 선호한다. 이해하기 쉽고 디버깅 하기도 쉬워 오류가 적다.

lumuto partition quick sort

Python

import random

def pivot(arr, lo, hi):
    p = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < p:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

def qsort(arr, left, right):
    mid = pivot(arr, left, right)
    if left < mid - 1:
        qsort(arr, left, mid - 1)
    if mid + 1 < right:
        qsort(arr, mid + 1, right)

for _ in range(100000):
    arr = [random.randint(1, 100) for _ in range(10)]
    expect = sorted(arr)
    qsort(arr, 0, len(arr) - 1)
    assert arr == expect

Java

private int pivot(long[] arr, int lo, int hi) {
    long pivot = arr[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            long tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
        }
    }
    long tmp = arr[i];
    arr[i] = arr[hi];
    arr[hi] = tmp;
    return i;
}

private void qsort(long[] arr, int lo, int hi) {
    int mid = pivot(arr, lo, hi);
    if (mid + 1 < hi) {
        qsort(arr, mid + 1, hi);
    }
    if (lo < mid - 1) {
        qsort(arr, lo, mid - 1);
    }
}