kth_item.py

kth_item.py

import time, random

def partition(myList, start, end):
    pivot = myList[start]
    left = start+1
    right = end
    done = False
    
    while not done:
        while left <= right and myList[left] <= pivot:
            left = left + 1
        while myList[right] >= pivot and right >=left:
            right = right -1
        if right < left:
            done= True
        else:
            temp=myList[left]
            myList[left]=myList[right]
            myList[right]=temp

    temp=myList[start]
    myList[start]=myList[right]
    myList[right]=temp
    return right
    

arr = list()
size = 10
for i in range(0, size):
	arr.append(random.randint(0,10000))
print arr

k = 4

s = 0
e = len(arr)-1
while True:
	i = partition(arr, s, e)
	if i==k:
		print arr
		print arr[i]
		break
	elif i<k:
		s = i+1 
	else:
		e = i-1