quickselect
Advanced tools
Comparing version 1.0.0 to 1.0.1
16
index.js
'use strict'; | ||
module.exports = partialSort; | ||
module.exports = quickselect; | ||
module.exports.default = quickselect; | ||
// Floyd-Rivest selection algorithm: | ||
// Rearrange items so that all items in the [left, k] range are smaller than all items in (k, right]; | ||
// The k-th element will have the (k - left + 1)th smallest value in [left, right] | ||
function quickselect(arr, k, left, right, compare) { | ||
quickselectStep(arr, k, left || 0, right || (arr.length - 1), compare || defaultCompare); | ||
}; | ||
function partialSort(arr, k, left, right, compare) { | ||
left = left || 0; | ||
right = right || (arr.length - 1); | ||
compare = compare || defaultCompare; | ||
function quickselectStep(arr, k, left, right, compare) { | ||
@@ -23,3 +21,3 @@ while (right > left) { | ||
var newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd)); | ||
partialSort(arr, k, newLeft, newRight, compare); | ||
quickselectStep(arr, k, newLeft, newRight, compare); | ||
} | ||
@@ -26,0 +24,0 @@ |
{ | ||
"name": "quickselect", | ||
"version": "1.0.0", | ||
"version": "1.0.1", | ||
"description": "A tiny and fast selection algorithm in JavaScript.", | ||
@@ -16,5 +16,13 @@ "main": "index.js", | ||
}, | ||
"keywords": ["selection", "algorithm", "quickselect", "sort", "partial", "floyd", "rivest"], | ||
"keywords": [ | ||
"selection", | ||
"algorithm", | ||
"quickselect", | ||
"sort", | ||
"partial", | ||
"floyd", | ||
"rivest" | ||
], | ||
"author": "Vladimir Agafonkin", | ||
"license": "ISC" | ||
} |
@@ -1,2 +0,2 @@ | ||
## quickselect | ||
## quickselect [![Build Status](https://travis-ci.org/mourner/quickselect.svg?branch=master)](https://travis-ci.org/mourner/quickselect) | ||
@@ -23,5 +23,7 @@ A tiny and fast [selection algorithm](https://en.wikipedia.org/wiki/Selection_algorithm) in JavaScript | ||
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] | ||
// ^^ 8th item | ||
// arr is [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95] | ||
// ^^ middle index | ||
``` |
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
3848
6
66
29