quickselect

What is quickselect?

The quickselect npm package is a fast selection algorithm implementation for JavaScript, based on Tony Hoare's quickselect algorithm. It allows for efficiently selecting the k-th smallest element from an unsorted list without fully sorting the array. This can be particularly useful in applications where partial sorting is sufficient, such as finding the median or other order statistics in a dataset.

What are quickselect's main functionalities?

Selecting the k-th smallest element

This feature allows you to rearrange the array so that the element at the k-th position is the one that would be in that position if the array were sorted. The elements before it are smaller, and the elements after it are larger. This is useful for finding specific order statistics, such as the median, in linear time.

const quickselect = require('quickselect');
let arr = [5, 3, 7, 6, 2, 9];
quickselect(arr, 2);
console.log(arr[2]); // Outputs: 5

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.

README

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