Quicksort 변형

quick sort는 pivot(기준점)을 정한 뒤에 작은 영역(smaller partition), 큰 영역(bigger partition)을 나누는 작업을 반복하는 것이다.

 

가독성 좋고 편한 quik sort 코드이다. 단점으로는 메모리를 이용한다는 것이다.

 

- 메모리 이용

def sort(array=[12,4,5,6,7,3,1,15]):
    """Sort the array by using quicksort."""

    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        return sort(less)+equal+sort(greater)
    else: 
        return array



print(sort([2,2,6,0,10]))

 

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

- 정식

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

 

참고

- https://www.youtube.com/watch?v=7BDzle2n47c

- https://stackoverflow.com/questions/18262306/quicksort-with-python