def swap(A, i, j):
A[i], A[j] = A[j], A[i]
def partition(A, p, r):
pivot = A[r]
i = p - 1
for j in range(p, r):
if A[j] <= pivot:
i += 1
swap(A, j, i)
swap(A, i+1, r)
print(A, i+1, pivot)
return i + 1
def randomized_partition(A, p, r):
randomidx = random.randrange(r-p+1) + p
swap(A, randomidx, r)
return partition(A, p, r)
def randomized_selection(A, p, r, s):
if p == r:
print(A)
return A[p]
q = randomized_partition(A, p, r)
k = q - p + 1
print(f"q:{q}, k:{k}, s:{s}, p:{p}, r:{r}")
if s == k:
print(A)
return A[q]
elif s < k:
return randomized_selection(A, p, q - 1, s)
else:
return randomized_selection(A, q + 1, r, s-k)
li =[6, 2, 7, 4, 9, 1, 5, 8, 3, 6]
print(randomized_selection(li, 0, 9, 3))