Something went wrong. Try again.
[READ-ONLY] Mirror of https://github.com/flo-bit/shapecraft. flo-bit.dev/shapecraft
Something went wrong. Try again.
3.6 kB · 114 lines
JavaScript
at commit da69385e
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115/* -*- 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);};