-
Notifications
You must be signed in to change notification settings - Fork 5
/
Improving QuickSort.py
52 lines (43 loc) · 1.21 KB
/
Improving 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
45
46
47
48
49
50
51
52
>>
import random
def partition3(a, left, right):
pivot_value = a[left]
p_l = i = left
p_e = right
while i <= p_e:
if a[i] < pivot_value:
a[i], a[p_l] = a[p_l], a[i]
p_l += 1
i += 1
elif a[i] == pivot_value:
i += 1
else:
a[i], a[p_e] = a[p_e], a[i]
p_e -= 1
pIndexes = [p_l, p_e]
return pIndexes
def partition2(a, left, right):
pivot = random.randint(left, right)
a[right], a[pivot] = a[pivot], a[right]
pivot_value = a[right]
pIndex = left
for i in range(left, right):
if a[i] <= pivot_value:
a[i], a[pIndex] = a[pIndex], a[i]
pIndex += 1
a[right], a[pIndex] = a[pIndex], a[right]
return pIndex
def randomized_quick_sort(a, left, right):
if left >= right:
return
pivot = random.randint(left, right)
a[left], a[pivot] = a[pivot], a[left]
pIndex = partition3(a, left, right)
randomized_quick_sort(a, left, pIndex[0] - 1)
randomized_quick_sort(a, pIndex[1] + 1, right)
n = int(input())
a = list(map(int, input().split()))
randomized_quick_sort(a, 0, n - 1)
for x in a:
print(x, end=' ')
@ CODED BY TSG405, 2021