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
53
54
55
56
57
58
59
60
|
# Uses python3
import sys
import random
def partition3(a, l, r):
x = a[l]
j = l
dupCount = 0
biggerNumCount = 0
for i in range(l + 1, r + 1):
if a[i] < x:
t = a[i]
a[j] = t
t = a[i - biggerNumCount]
a[i] = t
a[i - biggerNumCount] = x
j = j + 1
continue
if a[i] == x:
t = a[j + dupCount + 1]
a[i] = t
a[j + dupCount + 1] = x
dupCount = dupCount + 1
continue
biggerNumCount = biggerNumCount + 1
return (j, j + dupCount)
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)
(m1, m2) = partition3(a, l, r)
randomized_quick_sort(a, l, m1 - 1);
randomized_quick_sort(a, m2 + 1, r);
if __name__ == '__main__':
input = sys.stdin.read()
n, *a = list(map(int, input.split()))
randomized_quick_sort(a, 0, n - 1)
for x in a:
print(x, end=' ')
|
