forked from JimChengLin/JimCollection
-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuickSort.py
38 lines (28 loc) · 1.03 KB
/
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
from numbers import Number
from typing import List
sample = [-1, -5, 7, 19, -10, 7, 15, 19, -16, 20, -5, 19]
def partition(root: List[Number], index_from=0, index_to=None):
if index_to is None:
index_to = len(root) - 1
if index_from >= index_to:
return
pivot = root[index_to]
small_cursor = None
for current_cursor in range(index_from, index_to):
if root[current_cursor] < pivot:
if small_cursor is None:
small_cursor = index_from
else:
small_cursor += 1
if small_cursor != current_cursor:
root[small_cursor], root[current_cursor] = root[current_cursor], root[small_cursor]
if small_cursor is None:
small_cursor = index_from
else:
small_cursor += 1
root[index_to], root[small_cursor] = root[small_cursor], root[index_to]
if small_cursor < index_to:
partition(root, index_from, small_cursor - 1)
partition(root, small_cursor + 1, index_to)
partition(sample)
print(sample)