/
quick_sort.py
68 lines (50 loc) · 1.42 KB
/
quick_sort.py
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
66
67
68
#!/usr/bin/env python
def quick_sort(array):
if not array:
return
# sort(array, 0, len(array)-1)
sort3(array, 0, len(array)-1)
return array
# return sort2(array)
def sort(array, start, end):
if end < start:
return
elif end == start:
return
target = array[end]
less = start - 1
for m in range(start, end):
if array[m] < target:
less += 1
array[less], array[m] = array[m], array[less]
array[end], array[less+1] = array[less+1], array[end]
sort(array, start, less)
sort(array, less+2, end)
return
def sort2(array):
if not array:
return []
target = array[-1]
less = [x for x in array[:-1] if x < target]
greater = [x for x in array[:-1] if x >= target]
return sort2(less) + [target] + sort2(greater)
def sort3(array, start, end):
if start >= end:
return
target = array[end]
less, greater = start, end
while less < greater:
if array[less] >= target:
greater -= 1
array[less], array[greater] = array[greater], array[less]
else:
less += 1
array[greater], array[end] = array[end], array[greater]
sort3(array, start, greater-1)
sort3(array, greater+1, end)
return
if __name__ == "__main__":
array = [1]
print(quick_sort(array))
array = [25, 1, 8, 2, 5, 9, 25, 3, 2, 16]
print(quick_sort(array))