# How efficient to get pivot?

def get_pivot(array, left, right):
    # 현재 잘 안되고 있음
    if abs(left-right) > 2:
        mid = len(array) // 2
        first = 0
        last = len(array) - 1

        dic = {first: array[first],
               mid: array[mid],
               last: array[right]}
        min_ = array[first]
        max_ = array[last]
        for k, v in dic.items():
            if v < min_:
                min_ = k
            if v > max_:
                max_ = k
        pivot = [k for k, v in dic.items() if not dic[k] or not dic[k]][0]
        # print('')
    else:
        pivot = left
    pivot = left
    return pivot


def partition(array, left, right):
    pivot = get_pivot(array, left, right)
    while True:
        while array[left] <= array[pivot]:
            left += 1
        while array[right] > array[pivot]:
            right -= 1
        if left < right:
            array[left], array[right] = array[right], array[left]
        else:
            break
    array[pivot], array[right] = array[right], array[pivot]
    return right


def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    if begin >= end:
        return
    pivot = partition(array, begin, end)
    quicksort(array, begin, pivot-1)
    quicksort(array, pivot+1, end)


array = [54,26,93,17,77,31,31,44,55,20]
print(array)
quicksort(array)
print(array)
# [17, 20, 26, 31, 31, 44, 54, 55, 77, 93]