JavaScript - Sorting Algorithms(Quick sort, built-in sort function)

Data Structures and Algorithms With Javascript
(O'Reilly Media)
Michael McMillan(著)

開発環境

• OS X El Capitan - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• SpiderMonkey, Node.js(V8) (JavaScript engine)

Data Structures and Algorithms With Javascript (Michael McMillan(著)、O'Reilly Media)のChapter 12(Sorting Algorithms)、Exercises 4.(No. 5349)を解いてみる。

Exercises 4.(No. 5349)

JavaScript(Emacs)

/*jslint         browser : true, continue : true,
  devel  : true, indent  : 4,    maxerr   : 50,
  newcap : true, nomen   : true, plusplus : false,
  regexp : true, sloppy  : true, vars     : false,
  white  : true
*/

/*global */
var nums = [],
    quick_sort = function (ary) {
        var left = [],
            right = [],
            pivot,
            i,
            max;
        
        if (ary.length === 0) {
            return [];
        }
        pivot = ary[0];
        for (i = 1, max = ary.length; i < max; i += 1) {
            if (ary[i] < pivot) {
                left.push(ary[i]);
            } else {
                right.push(ary[i]);
            }
        }
        return quick_sort(left).concat(pivot, quick_sort(right));
    },
    start,
    stop,
    elements = 10000,
    sorted,
    i;

for (i = 0; i < elements; i += 1) {
    nums[i] = Math.floor(Math.random() * elements);
}

console.log('Quicksort');
start = new Date().getTime();
sorted = quick_sort(nums);
stop = new Date().getTime();
console.log('The elapsed time was: ' + (stop - start) + ' millseconds.');

console.log('built-in sorting function');
start = new Date().getTime();
nums.sort();
stop = new Date().getTime();
console.log('The elapsed time was: ' + (stop - start) + ' millseconds.');    

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample4.js

sample4.js is OK.
$ node sample4.js
Quicksort
The elapsed time was: 199 millseconds.
built-in sorting function
The elapsed time was: 77 millseconds.
$ node sample4.js
Quicksort
The elapsed time was: 234 millseconds.
built-in sorting function
The elapsed time was: 77 millseconds.
$