/
Kgeneral.py
50 lines (38 loc) · 1.03 KB
/
Kgeneral.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
"""
Algorithm to blind sort if all elements are in
the set {0, ..., K - 1} for some 0 < K <= N.
"""
from BlindArray import BlindArray
def sort(A):
N = len(A)
K = A.K
def partition(front):
"""
Puts all instances of the minimum element in A[front..].
"""
back = N - 1
while True:
while front < len(A) and A.is_frozen(front):
front += 1
while back >= 0 and A.is_frozen(back):
back -= 1
if front < back:
A.swap(front, back)
if A.is_frozen(front):
front += 1
back -= 1
else:
A.swap(front, back)
back -= 1
else:
break
return front
front = 0
for _ in range(K):
front = partition(front)
assert A.is_sorted()
def simulate(N=20, K=5, runs=100):
for _ in range(runs):
A = BlindArray(N, K)
sort(A)
simulate(N=20, K=20, runs=1000)