-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquick_sort.py
More file actions
40 lines (31 loc) · 1007 Bytes
/
quick_sort.py
File metadata and controls
40 lines (31 loc) · 1007 Bytes
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
from typing import List
def quick_sort(nums: List[int], left, right):
if left >= right:
return
mid = partition(nums, left, right)
quick_sort(nums, left, mid - 1)
quick_sort(nums, mid + 1, right)
def partition(nums, left, right):
# pivot = nums[right]
# index = left - 1
#
# for i in range(left, right):
# if nums[i] < pivot:
# index += 1
# nums[i], nums[index] = nums[index], nums[i]
# index += 1
# nums[index], nums[right] = nums[right], nums[index]
# return index
pivot_index = left
pivot_elem = nums[pivot_index]
for i in range(left + 1, right + 1):
if nums[i] < pivot_elem:
pivot_index += 1
nums[pivot_index], nums[i] = nums[i], nums[pivot_index]
nums[left], nums[pivot_index] = nums[pivot_index], nums[left]
return pivot_index
if __name__ == '__main__':
nums = [3, 6, 1, 5, 2, 4]
left, right = 0, 5
quick_sort(nums, left, right)
print(nums)