Kth_smallest_element.py

# Input:
# N = 6
# arr[] = 7 10 4 3 20 15
# K = 3
# Output : 7
# Explanation :
# 3rd smallest element in the given
# array is 7.

# def kthSmallest(arr, l, r, k):
#     '''
#     arr : given array
#     l : starting index of the array i.e 0
#     r : ending index of the array i.e size-1
#     k : find kth smallest element and return using this function
#     '''
#     arr.sort()
#     return(arr[k-1])

# r=int(input())
# arr=input()
# array=list(map(int,arr.strip().split()))
# k=int(input())
# print(kthSmallest(array,0,r-1,k))


def kthSmallest(arr, l, r, k):

    if k > 0 and k <= r - l + 1:

        pos = randomPartition(arr, l, r)
        if pos - l == k - 1:
            return arr[pos]
        if pos - l > k - 1:

            return kthSmallest(arr, l, pos - 1, k)

        return kthSmallest(arr, pos + 1, r, k - pos + l - 1)

    return 999999999999


def swap(arr, a, b):
    temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp


def partition(arr, l, r):
    x = arr[r]
    i = l
    for j in range(l, r):
        if arr[j] <= x:
            swap(arr, i, j)
            i += 1
    swap(arr, i, r)
    return i


def randomPartition(arr, l, r):
    n = r - l + 1
    pivot = int(random.random() % n)
    swap(arr, l + pivot, r)
    return partition(arr, l, r)