Pattern visualizer
Kth Largest Element in an Array
Sorting costs O(n log n) just to learn one order statistic. Quickselect partitions around a pivot like quicksort — but then recurses into ONLY the side that contains the answer. The kth largest is simply the element that ends up at ascending index n−k once partitions place pivots on their true sorted positions. Animated on: Find the 3rd largest element of [7,2,9,4,5,1,8] without fully sorting it..
Quickselect with Lomuto partition
time O(n) averagespace O(1)step 1 / 15
7
[0]2
[1]9
[2]4
[3]5
[4]1
[5]8
[6]line 1
k = 3 means the answer occupies ascending index n − k = 7 − 3 = 4. Goal: keep partitioning until some pivot lands EXACTLY on index 4.
Pseudocode
1FUNCTION quickselect(arr, lo, hi, k):2 pivot = arr[hi]; set boundary i to lo - 13 FOR j from lo to hi-1:4 IF arr[j] <= pivot:5 move i one step right, then swap arr[i] with arr[j]6 swap arr[i+1] with arr[hi] (pivot to its final spot)7 p = i + 18 IF p equals k: RETURN arr[p]9 IF p < k: quickselect on the right side (p+1, hi, k)10 ELSE: quickselect on the left side (lo, p-1, k)
← / → step · space play · Home restart