def partition(array, low, high):
    """
    This function takes last element as pivot, places
    the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
    to left of pivot and all greater elements to right
    of pivot.
    """
    pivot = array[high]
    i = low - 1
    j = low
    while j < high:

        if array[j] < pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

        j += 1
    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1