
def quickSort(nums, l, r):
    if l < r:
        partition_index = partition(nums, l, r)
        quickSort(nums, l, partition_index - 1)
        quickSort(nums, partition_index + 1, r)


def partition(nums, left, right):
    pivot = left
    index = pivot + 1
    i = index
    while i <= right:
        if nums[i] < nums[pivot]:
            swap(nums, i, index)
            index += 1
        i += 1
    swap(nums, pivot, index -1)
    return index - 1

def swap(nums, i, j):
    nums[i], nums[j] = nums[j], nums[i]


def quickSort2(nums, l, r):
    if l < r:
        partition_index = netherlandsFlag2(nums, l, r)
        quickSort(nums, l, partition_index[0] - 1)
        quickSort(nums, partition_index[-1] + 1, r)


def netherlandsFlag2(nums, l, r):
    if l > r:
        return [-1, -1]
    if l == r:
        return [l,r]
    pivot = l
    more = r
    index = pivot + 1
    less = index
    while index < more:
        if nums[index] == nums[pivot]:
            index += 1
        elif nums[index] < nums[pivot]:
            swap(nums, index, less)
            index += 1
            less += 1
        else:
            swap(nums, index, more)
            more -= 1
    swap(nums, index, pivot)
    return [less, more]
if __name__ == '__main__':
    nums = [9,5,6,7,8,3,2,1]
    quickSort2(nums, 0, len(nums) - 1)
    for ele in nums:
        print(ele)