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
Easily highlight source code for your blog with our Syntax Highlighter. 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