Finding the k-th smallest element use case.


Quickselect is a selection algorithm to find the k-th smallest (sometimes largest) element in an unordered list. It can be considered as subtype of quicksort sorting algorithm. In computer science Quickselect sometimes cakked Hoare's selection algorithm by the name of it's creator. It is considered very efficient in practice and has good average-case performance, but is not very good worst-case cases.

Quickselect algorithm.



The difference with quicksort is that after finding pivot instead of recurring for both sides, it recurs only for one side containing the k-th smallest element. The algorithm checks if index of the partitioned element is more than k it recurs for the left part, if index is less than k, then process recurs for the right part. When the index is equals k, then the k-th smallest element is found.


Quickselect algorithm Python code:




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

# ASSUMPTION: all elements in array are distinct
def kthSmallest(arr, l, r, k):
 
    # if k is smaller than number of elements in array
    if (k > 0 and k <= r - l + 1):
 
        # Partition the array around last element and get position of pivot element in sorted array
        index = partition(arr, l, r)
 
        # if position is same as k
        if (index - l == k - 1):
            return arr[index]
 
        # If position is more recur for left subarray
        if (index - l > k - 1):
            return kthSmallest(arr, l, index - 1, k)
 
        # Else recur for right subarray
        return kthSmallest(arr, index + 1, r,
                            k - index + l - 1)
    print("Index out of bound")
 
# Driver Code
arr = [ 1, 7, 5, 4, 6, 11, 26 ]
n = len(arr)
k = 3
print("K-th smallest element is ", end = "")
print(kthSmallest(arr, 0, n - 1, k))

OUT: K-th smallest element is 5





See also related topics: