ProgramGuru.org

ProgramGuru.org

Find Kth Smallest Element using Quickselect

Find Kth Smallest Element using Quickselect

Visualization

Algorithm Steps

  1. Given an array of numbers and an integer k (1-indexed), the goal is to find the kth smallest element.
  2. If the array contains only one element, return that element.
  3. Randomly choose a pivot from the array.
  4. Partition the array into three groups: lows (elements less than the pivot), pivots (elements equal to the pivot), and highs (elements greater than the pivot).
  5. If k is less than or equal to the size of lows, recursively search in lows.
  6. If k is within the size of lows plus pivots, the pivot is the kth smallest element.
  7. Otherwise, recursively search in highs with an updated k (subtracting the sizes of lows and pivots).

Quickselect Algorithm Program in Different Programming Languages Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
import random

def quickselect(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    lows = [x for x in arr if x < pivot]
    highs = [x for x in arr if x > pivot]
    pivots = [x for x in arr if x == pivot]
    if k <= len(lows):
        return quickselect(lows, k)
    elif k <= len(lows) + len(pivots):
        return pivot
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

if __name__ == '__main__':
    arr = [7, 10, 4, 3, 20, 15]
    k = 3
    print("The", k, "th smallest element is:", quickselect(arr, k))