-
Notifications
You must be signed in to change notification settings - Fork 0
/
quick_sort.py
68 lines (44 loc) · 1.34 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
'''quick sort in place
>>> lst = [5, 2, 1, 15, 10]
>>> print(quick_sort(lst))
[1, 2, 5, 10, 15]
>>> lst2 = [4, 6, 2, 3, 7 , 5, 10, 45, 23, 56, 89, 0]
>>> print(quick_sort(lst2))
[]
'''
def quick_sort(lst):
import random
def _quick_sort(lst, first, last):
pivot = lst[(first + last)//2]
#l - left index
#r - right index
l = first
r = last
left_found = False
right_found = False
print(l, r, pivot)
while l != r:
print(l, r, pivot)
print(lst)
if lst[l] >= pivot:
left_found= True
else:
l += 1
if lst[r] <= pivot:
right_found = True
else:
r -= 1
if left_found and right_found:
print('hi')
lst[l], lst[r] = lst[r],lst[l]
left_found = right_found = False
if first != l:
_quick_sort(lst, first, l - 1)
if l != last:
_quick_sort(lst, l+1, last)
print(len(lst)-1)
_quick_sort(lst, 0, len(lst)-1)
if __name__ == '__main__':
import doctest
if doctest.testmod().failed == 0:
print("\n*** ALL TESTS PASSED. GREAT WORK!\n")