Show More
Commit Description:
merge
Commit Description:
merge
References:
File last commit:
Show/Diff file:
Action:
node_modules/source-map/lib/quick-sort.js
| 114 lines
| 3.5 KiB
| application/javascript
| JavascriptLexer
|
| r789 | /* -*- Mode: js; js-indent-level: 2; -*- */ | |||
| /* | ||||
| * Copyright 2011 Mozilla Foundation and contributors | ||||
| * Licensed under the New BSD license. See LICENSE or: | ||||
| * http://opensource.org/licenses/BSD-3-Clause | ||||
| */ | ||||
| // It turns out that some (most?) JavaScript engines don't self-host | ||||
| // `Array.prototype.sort`. This makes sense because C++ will likely remain | ||||
| // faster than JS when doing raw CPU-intensive sorting. However, when using a | ||||
| // custom comparator function, calling back and forth between the VM's C++ and | ||||
| // JIT'd JS is rather slow *and* loses JIT type information, resulting in | ||||
| // worse generated code for the comparator function than would be optimal. In | ||||
| // fact, when sorting with a comparator, these costs outweigh the benefits of | ||||
| // sorting in C++. By using our own JS-implemented Quick Sort (below), we get | ||||
| // a ~3500ms mean speed-up in `bench/bench.html`. | ||||
| /** | ||||
| * Swap the elements indexed by `x` and `y` in the array `ary`. | ||||
| * | ||||
| * @param {Array} ary | ||||
| * The array. | ||||
| * @param {Number} x | ||||
| * The index of the first item. | ||||
| * @param {Number} y | ||||
| * The index of the second item. | ||||
| */ | ||||
| function swap(ary, x, y) { | ||||
| var temp = ary[x]; | ||||
| ary[x] = ary[y]; | ||||
| ary[y] = temp; | ||||
| } | ||||
| /** | ||||
| * Returns a random integer within the range `low .. high` inclusive. | ||||
| * | ||||
| * @param {Number} low | ||||
| * The lower bound on the range. | ||||
| * @param {Number} high | ||||
| * The upper bound on the range. | ||||
| */ | ||||
| function randomIntInRange(low, high) { | ||||
| return Math.round(low + (Math.random() * (high - low))); | ||||
| } | ||||
| /** | ||||
| * The Quick Sort algorithm. | ||||
| * | ||||
| * @param {Array} ary | ||||
| * An array to sort. | ||||
| * @param {function} comparator | ||||
| * Function to use to compare two items. | ||||
| * @param {Number} p | ||||
| * Start index of the array | ||||
| * @param {Number} r | ||||
| * End index of the array | ||||
| */ | ||||
| function doQuickSort(ary, comparator, p, r) { | ||||
| // If our lower bound is less than our upper bound, we (1) partition the | ||||
| // array into two pieces and (2) recurse on each half. If it is not, this is | ||||
| // the empty array and our base case. | ||||
| if (p < r) { | ||||
| // (1) Partitioning. | ||||
| // | ||||
| // The partitioning chooses a pivot between `p` and `r` and moves all | ||||
| // elements that are less than or equal to the pivot to the before it, and | ||||
| // all the elements that are greater than it after it. The effect is that | ||||
| // once partition is done, the pivot is in the exact place it will be when | ||||
| // the array is put in sorted order, and it will not need to be moved | ||||
| // again. This runs in O(n) time. | ||||
| // Always choose a random pivot so that an input array which is reverse | ||||
| // sorted does not cause O(n^2) running time. | ||||
| var pivotIndex = randomIntInRange(p, r); | ||||
| var i = p - 1; | ||||
| swap(ary, pivotIndex, r); | ||||
| var pivot = ary[r]; | ||||
| // Immediately after `j` is incremented in this loop, the following hold | ||||
| // true: | ||||
| // | ||||
| // * Every element in `ary[p .. i]` is less than or equal to the pivot. | ||||
| // | ||||
| // * Every element in `ary[i+1 .. j-1]` is greater than the pivot. | ||||
| for (var j = p; j < r; j++) { | ||||
| if (comparator(ary[j], pivot) <= 0) { | ||||
| i += 1; | ||||
| swap(ary, i, j); | ||||
| } | ||||
| } | ||||
| swap(ary, i + 1, j); | ||||
| var q = i + 1; | ||||
| // (2) Recurse on each half. | ||||
| doQuickSort(ary, comparator, p, q - 1); | ||||
| doQuickSort(ary, comparator, q + 1, r); | ||||
| } | ||||
| } | ||||
| /** | ||||
| * Sort the given array in-place with the given comparator function. | ||||
| * | ||||
| * @param {Array} ary | ||||
| * An array to sort. | ||||
| * @param {function} comparator | ||||
| * Function to use to compare two items. | ||||
| */ | ||||
| exports.quickSort = function (ary, comparator) { | ||||
| doQuickSort(ary, comparator, 0, ary.length - 1); | ||||
| }; | ||||