JavaScript - Sorting Algorithms(Selection sort, Insertion sort, Shell sort, Quick sort, String, times(Date object, getTime method))

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 1.(No. 8728)を解いてみる。

Exercises 1.(No. 8728)

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 CArray,
    quick_sort;

CArray = function (elements) {
    var i;
    
    this.data_store = [];
    this.pos = 0;
    this.elements = elements;    

    for (i = 0; i < elements; i += 1) {
        this.data_store[i] = i;
    }
};
CArray.prototype = {
    constructor: CArray,
    insert: function (element) {
        this.data_store[this.pos] = element;
        this.pos += 1;
    },
    toString: function () {
        var s = '',
            i,
            max;

        for (i = 0, max = this.data_store.length; i < max; i += 1) {
            s += this.data_store[i] + ' ';
            if (i > 0 && i % 10 === 0) {
                s += '\n';
            }
        }
        return s;
    },
    clear: function () {
        var i;

        for (i = 0; i < this.elements; i += 1) {
            this.data_store[i] = null;
        }
    },
    setData: function () {
        var arr = ['scheme', 'Scheme', 'scm', 'SCM', 'kscheme',
                   'JavaScript', 'js', 'JS', 'javascript', 'safari'],
            arr_len = arr.length,
            i;
        
        for (i = 0; i < this.elements; i += 1) {
            this.data_store[i] = arr[Math.floor(Math.random() * arr_len)];
        }
    },
    swap: function (index1, index2) {
        var temp = this.data_store[index1];

        this.data_store[index1] = this.data_store[index2];
        this.data_store[index2] = temp;
    },
    bubble_sort: function () {
        var elements = this.data_store.length,
            outer,
            inner;
        
        for (outer = elements; outer >= 2; outer -= 1) {
            for (inner = 0; inner <= outer - 1; inner += 1) {
                if (this.data_store[inner] > this.data_store[inner + 1]) {
                    this.swap(inner, inner + 1);
                }
            }
        }
    },
    selection_sort: function () {
        var min,
            outer,
            inner,
            len = this.data_store.length;

        for (outer = 0; outer <= len - 2; outer += 1) {
            min = outer;
            for (inner = outer + 1; inner <= len - 1; inner += 1) {
                if (this.data_store[inner] < this.data_store[min]) {
                    min = inner;
                }
            }
            this.swap(outer, min);
        }
    },
    insertion_sort: function () {
        var temp,
            inner,
            outer,
            len = this.data_store.length;

        for (outer = 1; outer <= len - 1; outer += 1) {
            temp = this.data_store[outer];
            inner = outer;
            while (inner > 0 && (this.data_store[inner - 1] >= temp)) {
                this.data_store[inner] = this.data_store[inner - 1];
                inner -= 1;
            }
            this.data_store[inner] = temp;
        }
    },
    shell_sort: function() {
        var gaps = [5, 3, 1],
            g,
            gaps_len = gaps.length,
            i,
            data_len = this.data_store.length,
            j,
            temp,
            gap;

        for (g = 0; g < gaps_len; g += 1) {
            for (i = gaps[g]; i < data_len; i += 1) {
                temp = this.data_store[i];
                gap = gaps[g];
                for (j = i; j >= gap && this.data_store[j - gap] > temp;
                     j -= gap) {
                    this.data_store[j] = this.data_store[j - gap];
                }
                this.data_store[j] = temp;
            }
        }
    }
};
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));
};

var elements = 10000,
    strs = new CArray(elements),
    start,
    stop,
    sorted;

console.log('Bubble sort');
strs.setData();
start = new Date().getTime();
strs.bubble_sort();
stop = new Date().getTime();
console.log('The elapsed time was: ' + (stop - start) + ' millseconds.');


console.log('Selection sort');
strs.setData();
start = new Date().getTime();
strs.selection_sort();
stop = new Date().getTime();
console.log('The elapsed time was: ' + (stop - start) + ' millseconds.');


console.log('Insertion sort');
strs.setData();
start = new Date().getTime();
strs.insertion_sort();
stop = new Date().getTime();
console.log('The elapsed time was: ' + (stop - start) + ' millseconds.');

console.log('Shell sort');
strs.setData();
start = new Date().getTime();
strs.shell_sort();
stop = new Date().getTime();
console.log('The elapsed time was: ' + (stop - start) + ' millseconds.');

console.log('Quick sort');
strs.setData();
start = new Date().getTime();
sorted = quick_sort(strs.data_store);
stop = new Date().getTime();
console.log('The elapsed time was: ' + (stop - start) + ' millseconds.');

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample1.js

sample1.js is OK.
$ node sample1.js
Bubble sort
The elapsed time was: 3015 millseconds.
Selection sort
The elapsed time was: 2320 millseconds.
Insertion sort
The elapsed time was: 953 millseconds.
Shell sort
The elapsed time was: 201 millseconds.
Quick sort
The elapsed time was: 675 millseconds.
$ node sample1.js
Bubble sort
The elapsed time was: 3132 millseconds.
Selection sort
The elapsed time was: 2377 millseconds.
Insertion sort
The elapsed time was: 978 millseconds.
Shell sort
The elapsed time was: 196 millseconds.
Quick sort
The elapsed time was: 716 millseconds.
$