SHARE
TWEET

Untitled

tinyevil Nov 28th, 2018 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* -*- Mode: js; js-indent-level: 2; -*- */
  2. /*  
  3.  * Copyright 2011 Mozilla Foundation and contributors
  4.  * Licensed under the New BSD license. See LICENSE or:
  5.  * http://opensource.org/licenses/BSD-3-Clause
  6.  */
  7.  
  8. // It turns out that some (most?) JavaScript engines don't self-host
  9. // `Array.prototype.sort`. This makes sense because C++ will likely remain
  10. // faster than JS when doing raw CPU-intensive sorting. However, when using a
  11. // custom comparator function, calling back and forth between the VM's C++ and
  12. // JIT'd JS is rather slow *and* loses JIT type information, resulting in
  13. // worse generated code for the comparator function than would be optimal. In
  14. // fact, when sorting with a comparator, these costs outweigh the benefits of
  15. // sorting in C++. By using our own JS-implemented Quick Sort (below), we get
  16. // a ~3500ms mean speed-up in `bench/bench.html`.
  17.  
  18. /**
  19.  * Swap the elements indexed by `x` and `y` in the array `ary`.
  20.  *
  21.  * @param {Array} ary
  22.  *        The array.
  23.  * @param {Number} x
  24.  *        The index of the first item.
  25.  * @param {Number} y
  26.  *        The index of the second item.
  27.  */
  28. function swap(ary, x, y) {
  29.   var temp = ary[x];
  30.   ary[x] = ary[y];
  31.   ary[y] = temp;
  32. }
  33.  
  34. /**
  35.  * Returns a random integer within the range `low .. high` inclusive.
  36.  *
  37.  * @param {Number} low
  38.  *        The lower bound on the range.
  39.  * @param {Number} high
  40.  *        The upper bound on the range.
  41.  */
  42. function randomIntInRange(low, high) {
  43.   return Math.round(low + (Math.random() * (high - low)));
  44. }
  45.  
  46. /**
  47.  * The Quick Sort algorithm.
  48.  *
  49.  * @param {Array} ary
  50.  *        An array to sort.
  51.  * @param {function} comparator
  52.  *        Function to use to compare two items.
  53.  * @param {Number} p
  54.  *        Start index of the array
  55.  * @param {Number} r
  56.  *        End index of the array
  57.  */
  58. function doQuickSort(ary, comparator, p, r) {
  59.   // If our lower bound is less than our upper bound, we (1) partition the
  60.   // array into two pieces and (2) recurse on each half. If it is not, this is
  61.   // the empty array and our base case.
  62.  
  63.   if (p < r) {
  64.     // (1) Partitioning.
  65.     //
  66.     // The partitioning chooses a pivot between `p` and `r` and moves all
  67.     // elements that are less than or equal to the pivot to the before it, and
  68.     // all the elements that are greater than it after it. The effect is that
  69.     // once partition is done, the pivot is in the exact place it will be when
  70.     // the array is put in sorted order, and it will not need to be moved
  71.     // again. This runs in O(n) time.
  72.  
  73.     // Always choose a random pivot so that an input array which is reverse
  74.     // sorted does not cause O(n^2) running time.
  75.     var pivotIndex = randomIntInRange(p, r);
  76.     var i = p - 1;
  77.  
  78.     swap(ary, pivotIndex, r);
  79.     var pivot = ary[r];
  80.  
  81.     // Immediately after `j` is incremented in this loop, the following hold
  82.     // true:
  83.     //
  84.     //   * Every element in `ary[p .. i]` is less than or equal to the pivot.
  85.     //
  86.     //   * Every element in `ary[i+1 .. j-1]` is greater than the pivot.
  87.     for (var j = p; j < r; j++) {
  88.       if (comparator(ary[j], pivot) <= 0) {
  89.         i += 1;
  90.         swap(ary, i, j);
  91.       }
  92.     }
  93.  
  94.     swap(ary, i + 1, j);
  95.     var q = i + 1;
  96.  
  97.     // (2) Recurse on each half.
  98.  
  99.     doQuickSort(ary, comparator, p, q - 1);
  100.     doQuickSort(ary, comparator, q + 1, r);
  101.   }
  102. }
  103.  
  104. /**
  105.  * Sort the given array in-place with the given comparator function.
  106.  *
  107.  * @param {Array} ary
  108.  *        An array to sort.
  109.  * @param {function} comparator
  110.  *        Function to use to compare two items.
  111.  */
  112. exports.quickSort = function (ary, comparator) {
  113.   doQuickSort(ary, comparator, 0, ary.length - 1);
  114. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top