[algorithm] quick sort code example

from random import random

def qsort(arr, n):
    _qsort(arr,0,n-1)

def _qsort(arr,first,last):
    if not first<last:
        return

    kl, kr = partition_first(arr,first,last)
    _qsort(arr,first,kl)
    _qsort(arr,kr,last)

def partition_first(arr,first,last):
    pivot = arr[first]
    i = first+1
    j = last

    while True:
        while not (arr[i] > pivot or i==j):
            i += 1
        while not (arr[j] < pivot or j<i):
            j -= 1

        if i>=j:
            break

        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1

    arr[first], arr[j] = arr[j], arr[first]
    return j-1, j+1

def partition_last(arr,first,last):
    pivot = arr[last]
    i = first
    j = last-1

    while True:
        while not (arr[i] > pivot or i>j):
            i += 1
        while not (arr[j] < pivot or j==i):
            j -= 1

        if i>=j:
            break

        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1

    arr[i], arr[last] = arr[last], arr[i]
    return i-1, i+1

if __name__ == '__main__':
    for i in range(10000):
        arr1 = [int(random()*10) for i in range(100)]
        arr2 = list(arr1)

        qsort(arr1, len(arr1))
        arr2.sort()

        assert arr1 == arr2
    print('done')

quick sort 함수 코드와, 중복이 있는 리스트로 함수를 검증하는 코드이다

quick sort는 크게 2번의 스텝으로 나뉘어진다

1. partition

2. recursion

partition 스텝에서는 리스트를 pivot 기준으로 less group / equal group / more group으로 정렬한다

recursion 스텝에서는 recursion을 통해 less group과 more group을 정렬한다

partition의 구현은 pivot이 first / center / last인 경우 3가지가 있다

위 코드에는 first인 경우, last인 경우 두 가지의 코드가 있다

pivot이 center인 경우, 3-way partition을 하려면 코드가 괜히 길어져서 제외했다

---

<구현과정>

구현을 할때, [5, 4, 3, 2, 1]과 [1, 2, 3, 4, 5] 2개의 테스트 케이스를 기준으로 하면 쉽다

수행과정을 생각해보면 loop의 조건이 명확해지기 때문이다

(작은 의미의 TDD:Test-Driven-Development?)