PYTHON

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]