퀵 정렬(Quick Sort)

def partitionH(start, end):
    pivot = start
    lp = start + 1
    rp = end
    while lp <= rp:
        while lp <= end and arr[pivot] >= arr[lp]:  # 값이 같았을 때도 포함해주자
            lp += 1
        while start <= rp and arr[pivot] < arr[rp]:
            rp -= 1
        if lp < rp:  # 같을 때는 교환하나마나
            arr[lp], arr[rp] = arr[rp], arr[lp]
    arr[rp], arr[pivot] = arr[pivot], arr[rp]
    return rp

def partitionL(start, end):
    pivot = end
    i = start - 1
    for j in range(start, end):
        if arr[pivot] > arr[j]:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    i += 1
    arr[pivot], arr[i] = arr[i], arr[pivot]
    return i

def quickSort(start, end):
    if start < end:
        # pivot = partitionH(start, end)
        pivot = partitionL(start, end)
        quickSort(start, pivot - 1)
        quickSort(pivot + 1, end)

arr = [5, 7, 8, 6, 4, 1, 2, 3, 9]
n = len(arr)
quickSort(0, n - 1)
print(arr)  # => [1, 2, 3, 4, 5, 6, 7, 8, 9]