License Public Domain
Lines 49
Keywords
quicksort (5) sort (5)
Implements this Algorithm
Permissions
Owner: Stou S.
Viewable by Everyone
Editable by All Siafoo Users
Hide
Need a quick chart or graph for your blog? Try our reStructured Text renderer. Join Siafoo Now or Learn More

Simple quick sort implementation Atom Feed 0

In Brief Can chose different pivot types by setting pivot_type
# 's
 1''' Quicksort implementation
2Author: stou@icapsid.net
3License: Public Domain
4'''
5
6from random import randint, shuffle
7
8comparisons = 0
9
10pivot_type = 0
11
12def pick_pivot(a):
13
14 if pivot_type == 0:
15 return 0
16 elif pivot_type == 1:
17 return len(a) - 1
18 elif pivot_type == 2:
19 middle = len(a) / 2 - 1 if len(a) % 2 == 0 else len(a) / 2
20
21 if a[-1] > a[0] and a[0] > a[middle]:
22 return 0
23 elif a[0] > a[-1] and a[-1] > a[middle]:
24 return -1
25 else:
26 return middle
27# elif pivot_type == 3:
28# return randint(0, len(a)-1)
29
30def quick_sort(a):
31
32 global comparisons
33
34 if len(a) > 0:
35 comparisons += (len(a) - 1)
36
37 if len(a) < 2:
38 return a
39
40 pivot_ix = pick_pivot(a)
41
42 a[0], a[pivot_ix] = a[pivot_ix], a[0]
43
44 i = 1
45
46 for j in range(1, len(a)):
47
48 if a[j] < a[0]:
49 a[j], a[i] = a[i], a[j]
50 i += 1
51
52 a[0], a[i - 1] = a[i - 1], a[0]
53
54 l_a = quick_sort(a[ : i - 1])
55 r_a = quick_sort(a[ i : ])
56
57 l_a.extend(r_a)
58
59 return l_a
60
61def main():
62
63 target = range(10)
64 shuffle(target)
65
66 target = [int(l) for l in open('QuickSort.txt').readlines()]
67
68 print quick_sort(target)
69
70 print comparisons
71
72if __name__ == '__main__':
73 main()

Can chose different pivot types by setting pivot_type