퀵(Quick) 정렬

나를 괴롭혔던 정렬 알고리즘. 병합정렬과 함께 가장 빠른 정렬 알고리즘이다.

다만 안정성은 병합정렬이 좋아서 대다수의 내장함수들은 병합정렬을 채택한다.

 

분명 2년전 자료구조 수업때 java로 구현해봐서 당연히 알고있다고 착각하고 있었다.

파이썬으로 간만에 재미삼아 구현하려니 안된다. 진짜 실력의 부족함을 매일 느낀다.

나는 언제쯤 잘해질 수 있을까.

 

추상적으로는 아래와 같은 절차를 따르면 된다.

1. pivot 원소 지정(어디든 상관 없음, 일반적으로 처음 or 끝 or 중간)

2. 배열 양끝단에 두개의 포인터를 지정한다. 일반적으로 i, j

3. 피벗원소보다 작은 원소는 왼쪽으로, 큰건 오른쪽으로 보낸다.

 - 원소 교체 후 i++, j--

4. 3번을 반복하다 i > j 가 엇갈리면 i 혹은 j를 기준으로 고정원소를 제외한 왼쪽 배열과 오른쪽 배열의 quick sort를 재귀적으로 호출

 

다른 블로그에서 코드를 몇개 봤는데 중복 원소에 대한 처리가 제대로 안된 것들이 보인다.

조심하자. 까다로운 부분이다. 아래 코드는 위키피디아에 공식적으로 올라온 inplace 방식의 퀵소트이다.

 

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high:
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list