#!/usr/local/bin/python3
# Author: Dr. Robert Heckendorn, Computer Science Department, University of Idaho, 2013

def partition(x) :
    return partitionaux(x, 0, len(x))

# WARNING: does not include value on right so you can use len(x) on right
def partitionaux(x, left, right) :
#    print((left, right))

    pivot = x[left]
    i = left
    j = right
    while (True) :
        i+=1
        while i<right-1 and x[i]<pivot :    # note the protection for over run on the right
            i+=1
        j-=1
        while x[j]>pivot :
            j-=1

        if i>=j : break
        (x[i], x[j]) = (x[j], x[i])
    (x[j], x[left]) = (x[left], x[j])
    return j

# y = [31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9, 50, 28, 8, 41]
# k = partition(y)
# print(k, y[k])
# print(y)
# 
# y = [2, 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9, 50, 28, 8, 41]
# k = partition(y)
# print(k, y[k])
# print(y)
# 
# y = [99, 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9, 50, 28, 8, 41]
# k = partition(y)
# print(k, y[k])
# print(y)
# 
# y = [42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42]
# k = partition(y)
# print(k, y[k])
# print(y)
# 
#