# Quick Select

Quick select determines the nth ranked item in an array without sorting the array. This is accomplished by recursively partitioning halves of the array until the nth item is placed in the correct position. A typical use is finding the nth highest score in an array.

## Asymptotic Complexity

$O(n)$ on average

## Pseudo Code

select:
// side effect: rearranges the values in A, the correct value will be in the
// nth position of the array
A = input array
nth = the nth highest value to find

if length of A <= 1:
return A

pivot_on = choose_pivot(n)
swap A with A[pivot_on]

pivot = partition(nth, A)

if pivot == nth:
return A[nth]

if pivot < nth:
return select(nth - pivot, A[pivot thru len of A])

return select(nth, A[0 thru pivot])

partition:
A = input array with the pivot value at position 0

pivot_pointer = A
left_pointer = A
right_pointer = A[last item]

infinite loop:
while
left_pointer < right_pointer and
left_pointer value < pivot_pointer value:

left_pointer + 1

while
right_pointer is not the begining of the array and
right_pointer value >= pivot_pointer value:

right_pointer + 1

if left_pointer >= right_pointer:
break out of infinite loop
else
swap left_pointer value with right_pointer value

swap pivot_pointer value with right_pointer value
return right_pointer

choose_pivot:
returns: ideal index to partition on
n = number of elements in the partition

return uniformly random number between 0 and n inclusive


Full Repo

Relevant Files: