Quicksort(1) : Quicksort

Quicksort

퀵정렬의 기본 개념은 다음과 같습니다.

• 우선 배열을 무작위로 섞고, 좌우 구간으로 나눕니다.
• 하나(i)는 왼쪽에서 오른쪽으로 이동하고, 나머지(j)는 오른쪽에서 왼쪽으로 이동합니다.
• i는 기준(partitioning element)보다 큰 값이 나오면, j는 기준보다 작은 값이 나오면 이동을 멈춥니다.
• 두 값을 교환합니다.
• 위 과정을 반복합니다.

퀵정렬은 합병 정렬이 그 자체로 수행되기 전에 분할하는 것과 달리, 퀵정렬은 분할마다 정렬이 수행된다는 차이점이 있습니다.

 

 

Quicksort partitioning demo

 

 

Quicksort: Java code for partitioning, Java implementation

def partition(a, lo, hi):
    i, j = lo, hi+1
    while True:
        i += 1
        while i < hi and less(a[i], a[lo]):
            i += 1

        j -= 1
        while j > lo and less(a[lo], a[j]):
            j -= 1

        if i >= j:
            break

        a[i],a[j] = a[j],a[i]

    a[lo],a[j] = a[j],a[lo]
    return j

import random

def partition(a, lo, hi):
    i, j = lo, hi+1
    while True:
        i += 1
        while i < hi and less(a[i], a[lo]):
            i += 1

        j -= 1
        while j > lo and less(a[lo], a[j]):
            j -= 1

        if i >= j:
            break

        exch(a, i, j)

    exch(a, lo, j)
    return j

def sort(a):
    random.shuffle(a)
    sort_helper(a, 0, len(a)-1)

def sort_helper(a, lo, hi):
    if hi <= lo:
        return

    j = partition(a, lo, hi)
    sort_helper(a, lo, j-1)
    sort_helper(a, j+1, hi)

아래 코드에서 exch는 사실 파이썬에 구현되어 있지 않은 함수라서, 위의 코드에서처럼 배열 내 두 원소의 값을 교환하는 형태로 변경하면 됩니다.

 

 

Quicksort trace

 

 

Quicksort: implementation details

퀵 정렬의 특징을 정리한 것은 위와 같습니다.

• in-place 정렬이기 때문에, aux array를 저장할 추가적인 메모리 공간이 필요한 합병 정렬에 비해 메모리 효율적입니다.
• while문의 종료조건을 이해하기가 단순히 보이는 것보다 조금 더 까다롭다고 합니다.
• 범위를 설정함에 있어서 j == lo 를 따지는 것은 불필요하다고 합니다.
• 퀵 정렬의 성능이 보장되기 위해서는 shuffle을 통해 randomness를 강화하는 것이 좋다고 합니다.

 

 

Quicksort: empirical analysis

분명히 합병 정렬과 동일한 시간 복잡도를 지녔음에도 불구하고, 실제로 처리에 필요한 시간은 퀵 정렬이 더 짧다는 것을 알 수 있습니다.

 

 

Quicksort: best/wort-case analysis

최악의 경우는 이미 정렬되어 있는 배열에 대해 퀵정렬을 수행할 때이지만, 위에서 언급한 것처럼 shuffle을 해줌으로써 이와 같은 경우는 사실상 발생하지 않는다고 볼 수 있습니다.

 

 

Quicksort: average-case analysis

평균(일반)적인 케이스의 연산 횟수에 대한 분석은 위와 같습니다.

정렬 과정의 N번째 비교 횟수를 Cn이라고 할 때 식을 정리한 과정입니다.

식은 위에 자세히 풀어져 있으니 결론만 간단히 말하자면, 평균적으로 NlogN의 시간복잡도를 갖는다,고 할 수 있습니다.

 

 

Quicksort: summary of performance characteristics

반복적으로 언급했다시피 최악의 경우 비교 횟수는 꽤나 증가할 수 있지만, 그런 경우를 방지하기 위해 shuffle을 포함합니다.

 

 

Quicksort properties

• 퀵 정렬은 원본 배열의 값을 변경하는 in-place 방식으로 정렬을 수행합니다.
• 퀵 정렬은 이전에 정렬된 값이 재배치 될 수도 있는 un-stable 정렬 알고리즘입니다.

 

 

Quicksort: practical improvements

퀵 정렬의 효율을 개선하기 위한 두 가지 방법을 제시하고 있습니다.

• 작은 하위 배열에 대해서는(재귀적으로 쪼갠 것) 삽입 정렬을 사용한다.
• pivot, 즉 partitioning element를 임의로 정하는 것보다 median(중간값)으로 정하는 것이 좋다.

 

 

 

출처: Coursera, Algorithms, Part 1, Princeton University