QuickSelect is a selection algorithm based on QuickSort's partition. Instead of sorting both halves, you only recurse into the half containing the th element.
Pick a pivot and partition the array.
If the pivot lands at position , you found the answer.
If pivot position , recurse left.
If pivot position , recurse right.
Average case is because you halve the problem each time: .