-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathkinoshita_quicksort.py
More file actions
59 lines (44 loc) · 1.31 KB
/
kinoshita_quicksort.py
File metadata and controls
59 lines (44 loc) · 1.31 KB
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
import copy
def quicksort(list_):
sorted_list = copy.copy(list_)
recursive_quicksort(sorted_list, 0, len(sorted_list))
return sorted_list
def recursive_quicksort(list_, start, stop):
if stop - start <= 1:
return
med_idx = (start + stop - 1) // 2
pivot = list_[med_idx]
i = start
j = stop - 1
while True:
while list_[i] < pivot:
i += 1
while list_[j] > pivot:
j -= 1
if i >= j:
break
list_[i], list_[j] = list_[j], list_[i]
i += 1
j -= 1
recursive_quicksort(list_, start, i)
recursive_quicksort(list_, j+1, stop)
return
if __name__ == "__main__":
list1 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
print(quicksort(list1))
print(quicksort(list1) == sorted(list1))
list1 = [1, 1, 1, 1, 0, 0, 0, 0]
print(quicksort(list1))
print(quicksort(list1) == sorted(list1))
list1 = [-1, 0, 1e-10, float("inf"), -float("inf")]
print(quicksort(list1))
print(quicksort(list1) == sorted(list1))
list1 = [0, 3, 2, 0, 4, 7, 5]
print(quicksort(list1))
print(quicksort(list1) == sorted(list1))
list1 = [1]
print(quicksort(list1))
print(quicksort(list1) == sorted(list1))
list1 = []
print(quicksort(list1))
print(quicksort(list1) == sorted(list1))