quickselect

quickselect(arr, k, left?, right?): void

Defined in: src/quickselect.js:17

Rearrange items in arr so that all items in [left, k] range are the smallest. The k-th element will have the (k - left + 1)-th smallest value in [left, right].

Implements Floyd-Rivest selection algorithm https://en.wikipedia.org/wiki/Floyd-Rivest_algorithm

Parameters

arr

number[]

input array

k

number

pivot index

left?

number

left index

right?

number

right index

Returns

void

mutates input array

Example

var arr = [65, 28, 59, 33, 21, 56, 22, 95, 50, 12, 90, 53, 28, 77, 39];
quickselect(arr, 8);
// = [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95]