Random Select Algo
# ------------------- Randomized selection
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 # index of the new position of the pivot which is his good position in the sorted array
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): # s is the nth element of the arr sorted ex: s=2 => A[1]
#p is the index of the first element/ r the last
if p == r:
print(A)
return A[p]
q = randomized_partition(A, p, r)
k = q - p + 1 # length between p and q
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)
#-----------Code
li =[6, 2, 7, 4, 9, 1, 5, 8, 3, 6]
print(randomized_selection(li, 0, 9, 3))
# The 3rd element is 3
#sorted li : [1, 2, 3, 4, 5, 6, 6, 7, 8, 9]
Disturbed Deer