-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathsorting.py
More file actions
36 lines (30 loc) · 740 Bytes
/
sorting.py
File metadata and controls
36 lines (30 loc) · 740 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
# Uses python3
import sys
import random
def partition3(a, l, r):
#write your code here
pass
def partition2(a, l, r):
x = a[l]
j = l
for i in range(l + 1, r + 1):
if a[i] <= x:
j += 1
a[i], a[j] = a[j], a[i]
a[l], a[j] = a[j], a[l]
return j
def randomized_quick_sort(a, l, r):
if l >= r:
return
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
#use partition3
m = partition2(a, l, r)
randomized_quick_sort(a, l, m - 1);
randomized_quick_sort(a, m + 1, r);
if __name__ == '__main__':
input = sys.stdin.readline()
n, *a = list(map(int, input.split()))
randomized_quick_sort(a, 0, n - 1)
for x in a:
print(x, end=' ')