#!/usr/bin/env python
import sys
import random

def swap(a, b):
	return b, a

def shell_sort(array):
	lens = len(array)
	step = lens/2
	while step >= 1:
		# print step
		# print range(step, lens)
		for i in range(step, lens):
			while i-step>=0:
				if array[i-step] > array[i]:
					array[i-step], array[i] = array[i], array[i-step]
					i = i-step
				else:
					break
		step = step/2

def qsort(array, l, u):
	if l >= u:
		return
	t = array[l]
	m = l+1
	for i in range(l+1, u+1):
		if array[i] < t:
			# swap(array[i], array[m])
			array[i], array[m] = array[m], array[i]
			m+=1
	# print m		
	# swap(array[l], array[m-1])
	array[l], array[m-1] = array[m-1], array[l]
	qsort(array, l, m-2)
	qsort(array, m, u)

def select(array, l, u, k):
	# print "l: %d u%d k%d" % (l,u,k)
	if k > len(array) or k < 0:
		# print 0
		return -1
	else:
		if l==u:
			# print 1
			return array[l]
		elif l>u:
			return -1
		t = array[l]
		m = l
		for i in range(l+1, u+1):
			if array[i] < t:
				array[i], array[m+1] = array[m+1], array[i]
				m+=1
		array[l], array[m] = array[m], array[l]
		print array
		print m
		if m+1 == k:
			# print 2, m, array[m]
			return array[m]
		elif m+1 > k:
			return select(array, l, m-1, k)
		else:
			return select(array, m+1, u, k)

def p(array, k):
	return array[k]

# list = random.sample(range(0,100), 20)
# print list

# shell_sort(list)
# print list

# qsort(list, 0, 19)
# print list

list = random.sample(range(0,100), 20)
a = list[:]
print list
# print p(list, 3)

v = select(list, 0, 19, 5)
print v
# print list[2]
# print list

qsort(a, 0, 19)
print a
# print list
