This is an automated email from the git hooks/post-receive script. sebastic pushed a commit to branch master in repository node-quickselect.
commit 508c9b5bd3cf4e2b8af168df57f053948acf6aa0 Author: Bas Couwenberg <[email protected]> Date: Sun Dec 24 12:25:51 2017 +0100 New upstream version 1.0.1 --- .travis.yml | 4 ++++ README.md | 8 +++++--- bench.js | 13 +++++++++++++ index.js | 16 +++++++--------- package.json | 12 ++++++++++-- 5 files changed, 39 insertions(+), 14 deletions(-) diff --git a/.travis.yml b/.travis.yml new file mode 100644 index 0000000..8131feb --- /dev/null +++ b/.travis.yml @@ -0,0 +1,4 @@ +language: node_js +node_js: + - "4" + - "stable" diff --git a/README.md b/README.md index 382bef6..a068f11 100644 --- a/README.md +++ b/README.md @@ -1,4 +1,4 @@ -## quickselect +## quickselect [](https://travis-ci.org/mourner/quickselect) A tiny and fast [selection algorithm](https://en.wikipedia.org/wiki/Selection_algorithm) in JavaScript (specifically, [Floyd-Rivest selection](https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm)). @@ -20,7 +20,9 @@ Example: ```js 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 ``` diff --git a/bench.js b/bench.js new file mode 100644 index 0000000..282c5cd --- /dev/null +++ b/bench.js @@ -0,0 +1,13 @@ +'use strict'; + +var quickselect = require('./'); + +var N = 10000000; +var arr = []; +for (var i = 0; i < N; i++) arr.push(Math.random()); + +console.time('quickselect'); +quickselect(arr, Math.floor(N / 2), 0, N - 1, function (a, b) { + return a < b ? -1 : a > b ? 1 : 0; +}); +console.timeEnd('quickselect'); diff --git a/index.js b/index.js index 7845738..be4740b 100644 --- a/index.js +++ b/index.js @@ -1,15 +1,13 @@ '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) { while (right > left) { if (right - left > 600) { @@ -20,7 +18,7 @@ function partialSort(arr, k, left, right, compare) { var sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1); var newLeft = Math.max(left, Math.floor(k - m * s / n + sd)); 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); } var t = arr[k]; diff --git a/package.json b/package.json index 4302979..54054b9 100644 --- a/package.json +++ b/package.json @@ -1,6 +1,6 @@ { "name": "quickselect", - "version": "1.0.0", + "version": "1.0.1", "description": "A tiny and fast selection algorithm in JavaScript.", "main": "index.js", "dependencies": {}, @@ -13,7 +13,15 @@ "pretest": "eslint index.js test.js", "test": "tape test.js" }, - "keywords": ["selection", "algorithm", "quickselect", "sort", "partial", "floyd", "rivest"], + "keywords": [ + "selection", + "algorithm", + "quickselect", + "sort", + "partial", + "floyd", + "rivest" + ], "author": "Vladimir Agafonkin", "license": "ISC" } -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-grass/node-quickselect.git _______________________________________________ Pkg-grass-devel mailing list [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-grass-devel
