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.
Python Knowledge Base: Make coding great again.
- Updated:
2024-07-26 by Andrey BRATUS, Senior Data Analyst.
Quickselect algorithm Python code:
Quickselect algorithm code output:
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.
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