Code Notes made by Vaibhav Rathod

Quick Select Algorithm

1 min read

Written by Vaibhav Rathod

Explanation

  • Quick Select is used to find the k-th smallest element in an unordered array. It is similar to QuickSort but only partially sorts the array.

Steps

  • Choose a pivot and partition the array such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.
  • If the pivot position is the k-th smallest, return it.
  • If the pivot position is greater than k, recursively search the left side; otherwise, search the right side.

Time Complexity

  • O(n) on average, O(n^2) in the worst case.
import random
 
def quick_select(arr, k):
    if len(arr) == 1:
        return arr[0]
 
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x > pivot]
    middle = [x for x in arr if x == pivot]
 
    if k < len(left):
        return quick_select(left, k)
    elif k < len(left) + len(middle):
        return middle[0]
    else:
        return quick_select(right, k - len(left) - len(middle))
 
# Example usage
arr = [7, 10, 4, 3, 20, 15]
k = 3
print(f"The {k+1}-th smallest element is:", quick_select(arr, k))

Graph View

Backlinks

Recently Updated