-
Notifications
You must be signed in to change notification settings - Fork 0
/
quickSort.py
44 lines (34 loc) · 873 Bytes
/
quickSort.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
import numpy as np
def swap(data, i, j):
data[i], data[j] = data[j], data[i]
def qsort3(data, left, right):
# sorted
if left >= right:
return
# select pivot
i = np.random.randint(left, right + 1)
swap(data, left, i)
pivot = data[left]
# i ~ points behind left partition
# j ~ points ahead of right partition
# k ~ current element
i, j, k = left, right, left + 1
# split to [left] + [pivot] + [right]
while k <= j:
if data[k] < pivot:
swap(data, i, k)
i += 1
elif data[k] > pivot:
swap(data, j, k)
j -= 1
k -= 1
k += 1
# recursion
qsort3(data, left, i - 1)
qsort3(data, j + 1, right)
def qsort(data):
qsort3(data, 0, len(data) - 1)
data = np.random.randint(0, 10, 100)
print(data)
qsort(data)
print(data)