quickselect

quickselect

A tiny and fast selection algorithm in JavaScript (specifically, Floyd-Rivest selection).

quickselect(array, k[, left, right, compareFn]);

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

• array: the array to partially sort (in place)
• k: middle index for partial sorting (as defined above)
• left: left index of the range to sort (0 by default)
• right: right index (last index of the array by default)
• compareFn: compare function

Example:

const arr = [65, 28, 59, 33, 21, 56, 22, 95, 50, 12, 90, 53, 28, 77, 39];

quickselect(arr, 8);

// arr is [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95]
//                                         ^^ middle index

Similar packages

Other packages similar to quickselect

heap

The 'heap' package provides a way to create min and max heaps in JavaScript. While not directly offering the same functionality as quickselect, heaps can be used to efficiently find the k-th smallest or largest element by inserting elements into the heap and then extracting the minimum or maximum k times. This approach is more suited for streaming data or when multiple order statistics need to be found over time.

simple-statistics

The 'simple-statistics' package offers a wide range of statistical functions, including a method for finding the median. While it does not provide a direct implementation of the quickselect algorithm, it uses sorting and other techniques to calculate various statistics, which can be useful in data analysis scenarios where more than just order statistics are needed.