Algorithms/linearselect.py at master · streethacker/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#/usr/bin/python
#-*- coding:utf-8 -*-

import random

def InsertionSort(a, p, r):
	for i in range(1, r):
			val = a[i]
			pos = i
	while pos > 0 and val < a[pos-1]:
			a[pos] = a[pos-1]
			pos -= 1

	a[pos] = val

def partition(a, p, r, x):
	i, j = p, r
	while i < j:
			if a[i] > x:
					while i < j and a[j] > x:
							j -= 1
					if i != j:
							a[i], a[j] = a[j], a[i]
							j -= 1
			i += 1
	return i-1

def LinearSelect(a, p, r, k):
	if r-p < 75:
			InsertionSort(a, p, r)
			return a[p+k-1]
	for i in range((r-p-4)/5+1):
			s, t = p+5*i, p+5*i+4
			InsertionSort(a, s, t)
			a[p+i], a[s+2] = a[s+2], a[p+i]

	x = LinearSelect(a, p, p+(r-p-4)/5, (r-p-4)/10)

	i = partition(a, p, r, x)
	j = i - p + 1

	if k<j:
			return LinearSelect(a, p, i, k)
	elif k==j:
			return a[j]
	else:
			return LinearSelect(a, i+1, r, k-j)


if __name__ == "__main__":
		array = list()
		for i in range(500):
				if i % 10 == 0:	print
				array.append(random.randint(0,1000))
				print array[i], "\t",

		print
		print

		k = input("Please input the rank k:")

		print "The %s(st,nd,rd or th) smallest number is: " % k, LinearSelect(array, 0, 499, k)