[node-quickselect] 01/04: Imported Upstream version 1.0.0

[Bas Couwenberg]

This is an automated email from the git hooks/post-receive script.

sebastic pushed a commit to branch master
in repository node-quickselect.

commit cb9854ca864452483e929e5c9784506c7d9b4583
Author: Bas Couwenberg <sebastic at xs4all.nl>
Date:   Wed Jun 29 23:11:08 2016 +0200

    Imported Upstream version 1.0.0
---
 README.md    | 26 ++++++++++++++++++++++++++
 index.js     | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 package.json | 19 +++++++++++++++++++
 test.js      | 11 +++++++++++
 4 files changed, 116 insertions(+)

diff --git a/README.md b/README.md
new file mode 100644
index 0000000..382bef6
--- /dev/null
+++ b/README.md
@@ -0,0 +1,26 @@
+## 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)).
+
+```js
+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:
+
+```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
+```
diff --git a/index.js b/index.js
new file mode 100644
index 0000000..7845738
--- /dev/null
+++ b/index.js
@@ -0,0 +1,60 @@
+'use strict';
+
+module.exports = partialSort;
+
+// 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 partialSort(arr, k, left, right, compare) {
+    left = left || 0;
+    right = right || (arr.length - 1);
+    compare = compare || defaultCompare;
+
+    while (right > left) {
+        if (right - left > 600) {
+            var n = right - left + 1;
+            var m = k - left + 1;
+            var z = Math.log(n);
+            var s = 0.5 * Math.exp(2 * z / 3);
+            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);
+        }
+
+        var t = arr[k];
+        var i = left;
+        var j = right;
+
+        swap(arr, left, k);
+        if (compare(arr[right], t) > 0) swap(arr, left, right);
+
+        while (i < j) {
+            swap(arr, i, j);
+            i++;
+            j--;
+            while (compare(arr[i], t) < 0) i++;
+            while (compare(arr[j], t) > 0) j--;
+        }
+
+        if (compare(arr[left], t) === 0) swap(arr, left, j);
+        else {
+            j++;
+            swap(arr, j, right);
+        }
+
+        if (j <= k) left = j + 1;
+        if (k <= j) right = j - 1;
+    }
+}
+
+function swap(arr, i, j) {
+    var tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+}
+
+function defaultCompare(a, b) {
+    return a < b ? -1 : a > b ? 1 : 0;
+}
diff --git a/package.json b/package.json
new file mode 100644
index 0000000..4302979
--- /dev/null
+++ b/package.json
@@ -0,0 +1,19 @@
+{
+  "name": "quickselect",
+  "version": "1.0.0",
+  "description": "A tiny and fast selection algorithm in JavaScript.",
+  "main": "index.js",
+  "dependencies": {},
+  "devDependencies": {
+    "eslint": "^2.1.0",
+    "eslint-config-mourner": "^2.0.0",
+    "tape": "^4.4.0"
+  },
+  "scripts": {
+    "pretest": "eslint index.js test.js",
+    "test": "tape test.js"
+  },
+  "keywords": ["selection", "algorithm", "quickselect", "sort", "partial", "floyd", "rivest"],
+  "author": "Vladimir Agafonkin",
+  "license": "ISC"
+}
diff --git a/test.js b/test.js
new file mode 100644
index 0000000..3bf22a5
--- /dev/null
+++ b/test.js
@@ -0,0 +1,11 @@
+'use strict';
+
+var test = require('tape').test;
+var quickselect = require('./');
+
+test('selection', function (t) {
+    var arr = [65, 28, 59, 33, 21, 56, 22, 95, 50, 12, 90, 53, 28, 77, 39];
+    quickselect(arr, 8);
+    t.deepEqual(arr, [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95]);
+    t.end();
+});

-- 
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-grass/node-quickselect.git