1
2
3
4
5
6
7
8 """
9 This module provides a variety of list sorting algorithms, to
10 illustrate the many different algorithms (recipes) for solving a
11 problem, and how to analyze algorithms experimentally.
12 """
13
14
15
16
17
18
19
20
21
23 """
24 Selection Sort: scan the list to find its smallest element, then
25 swap it with the first element. The remainder of the list is one
26 element smaller; apply the same method to this list, and so on.
27 """
28 count = 0
29
30 for i in range(len(a) - 1):
31 min = i
32
33 for j in range(i+1, len(a)):
34 if a[j] < a[min]:
35 min = j
36
37 count += 1
38
39 a[min],a[i] = a[i],a[min]
40
41 return count
42
43
44
45
46
48 """
49 Bubble Sort: compare adjacent elements of the list left-to-right,
50 and swap them if they are out of order. After one pass through
51 the list swapping adjacent items, the largest item will be in
52 the rightmost position. The remainder is one element smaller;
53 apply the same method to this list, and so on.
54 """
55 count = 0
56 for i in range(len(a)-1):
57 for j in range(len(a)-i-1):
58 if a[j+1] < a[j]:
59 a[j],a[j+1] = a[j+1],a[j]
60 count += 1
61 return count
62
63
64
65
66
67
69 count = 0
70 i = j = 0
71 a = []
72 while (i < len(b) and j < len(c)):
73 count += 1
74 if b[i] <= c[j]:
75 a.append(b[i])
76 i += 1
77 else:
78 a.append(c[j])
79 j += 1
80 if i == len(b):
81 a += c[j:]
82 else:
83 a += b[i:]
84 return a, count
85
87 """
88 Merge Sort: split the list in half, and sort each half, then
89 combine the sorted halves.
90 """
91 count = 0
92 if len(a) > 1:
93 midpoint = len(a)/2
94 b = a[:midpoint]
95 c = a[midpoint:]
96 count_b = merge(b)
97 count_c = merge(c)
98 a, count_a = _merge_lists(b, c)
99 count = count_a + count_b + count_c
100 return count
101
102
103
104
105
107 p = a[l]; i = l; j = r+1
108 count = 0
109 while True:
110 while i < r:
111 i += 1
112 if a[i] >= p: break
113 while j > l:
114 j -= 1
115 if j < l or a[j] <= p: break
116 a[i],a[j] = a[j],a[i]
117 count += 1
118 if i >= j: break
119 a[i],a[j] = a[j],a[i]
120 a[l],a[j] = a[j],a[l]
121 return j, count
122
130
133
134
135
136
137
139 from random import shuffle
140
141 for size in (10, 20, 50, 100, 200, 500, 1000):
142 a = range(size)
143
144
145 shuffle(a); count_selection = selection(a)
146 shuffle(a); count_bubble = bubble(a)
147 shuffle(a); count_merge = merge(a)
148 shuffle(a); count_quick = quick(a)
149
150 print "size=%5d: selection=%8d, bubble=%8d, merge=%6d, quick=%6d" %\
151 (size, count_selection, count_bubble, count_merge, count_quick)
152
153 if __name__ == '__main__':
154 demo()
155