@saehrimnir/druidjs / quickselect

Function: quickselect()

function quickselect<T>(
   arr: T[], 
   randomizer: Randomizer, 
   k: number, 
   compareFn?: (a: T, b: T) => number, 
   start_left?: number, 
   start_right?: number): T;

Defined in: util/quickselect.js:44

In-place QuickSelect algorithm to partition an array around the k-th smallest element. Runs in O(N) average time complexity (compared to O(N log N) for full Array.prototype.sort).

After the call arr[k] holds the k-th smallest element, every element left of k compares less than or equal to it, and every element right of k compares greater than or equal to it.

Type Parameters

Type Parameter	Description
T

Parameters

Parameter	Type	Default value	Description
arr	T[]	undefined	Array to partition in-place
randomizer	Randomizer	undefined	Seeded source of randomness for pivot selection.
k	number	undefined	Target 0-indexed rank to select
compareFn?	(a: T, b: T) => number	defaultCompare	Comparison function
start_left?	number	0	Start index (inclusive)
start_right?	number	...	End index (inclusive)

Returns

T

The k-th smallest element in the array