Fast implementation of median search using quickselect algorithm
npm install median-quickselectFast implementation of lower median search using Quick select algorithm. Ported from this C implementation.
Please read "Fast median search: an ANSI C implementation" by Nicolas Devillard for more info.
Note that result can be different from other packages, as median-quickselect calculates lower median, because taking an average of the two central elements requires two calls to the routine, doubling the processing time.
shell
npm install --save median-quickselect
`
Or hot-link via unpkg.com
html
`
Usage
js
const median = require('median-quickselect');
median([1, 4, 10, 2, 5, 0, -5]); // 2
`
Note that the order of elements on array passed to will be changed after call.
Benchmark
`
$ npm run bench 1001 ms master > node test/benchmark.js
benchmarking dataset of 100 numbers
median: 0.891ms
fast-median: 0.999ms
compute-median: 0.269ms
stats-median: 0.159ms
median-quickselect: 0.230ms
benchmarking dataset of 1000 numbers
median: 0.849ms
fast-median: 1.713ms
compute-median: 0.562ms
stats-median: 0.210ms
median-quickselect: 0.204ms
benchmarking dataset of 10000 numbers
median: 6.249ms
fast-median: 9.413ms
compute-median: 5.816ms
stats-median: 5.101ms
median-quickselect: 2.027ms
benchmarking dataset of 1000000 numbers
median: 576.688ms
fast-median: 886.843ms
compute-median: 786.714ms
stats-median: 662.177ms
median-quickselect: 13.027ms
benchmarking dataset of 10000000 numbers
median: 6347.193ms
fast-median: 8722.377ms
compute-median: 7278.490ms
stats-median: 7089.452ms
median-quickselect: 119.298ms