import os
import random
import sys


def main(env, prog, argv):
    # Set the seed constant, we will have the same result every time
    random.seed(1)
    elements = generate_unsorted_elements(10)
    deep = 0
    print(elements)
    quicksort(deep, 0, len(elements) - 1, elements)
    print(elements)


def quicksort(deep, left, right, elements):
    print(
        ' ' * deep * 4,
        'quicksort({!r}, {!r}, {!r}, {!r})'.format(deep, left, right, elements[left:right+1])
    )

    if left < right:
        p = partition(deep + 1, elements, left, right)
        quicksort(deep + 1, left, p - 1, elements)
        quicksort(deep + 1, p + 1, right, elements)
    print(
        ' ' * deep * 4,
        ' <- {!r}'.format(elements[left:right+1])
    )


def partition(deep, elements, left, right):
    pivot = elements[right]
    i = left - 1
    for j in range(left, right):
        if elements[j] < pivot:
            i += 1
            swap(elements, i, j)
    if elements[right] < elements[i+1]:
        swap(elements, i + 1, right)
    return i + 1


def swap(elements, index1, index2):
    tmp = elements[index1]
    elements[index1] = elements[index2]
    elements[index2] = tmp


def generate_unsorted_elements(n=100):
    elements = list(range(n))
    random.shuffle(elements)
    return elements


if __name__ == '__main__':
    main(os.environ, sys.argv[0], sys.argv[1:])