2015年10月26日月曜日

開発環境

  • 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 3.(No. 8802)を解いてみる。

Exercises 3.(No. 8802)

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 i,
            max;

        // for (i = 0, max = this.elements; i < max; i += 1) {
        //     this.data_store[i] = Math.floor(
        //         Math.random() * (this.elements + 1));
        // }
        for (i = 0, max = this.elements; i < max; i += 1) {
            this.data_store[i] = this.elements - i - 1;
        }
    },
    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 () {
        var inner = 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 inner(left).concat(pivot, inner(right));
        };
        return inner(this.data_store);
    },
    merge_sort: function () {
        var inner = function (ary) {
            var step = 1,
                left,
                right,
                merge_arrays = function (ary, start_left, stop_left,
                                         start_right, stop_right) {
                    var right_ary = new Array(stop_right - start_right + 1),
                        left_ary = new Array(stop_left - start_left + 1),
                        k = start_right,
                        i,
                        max,
                        m = 0,
                        n = 0;

                    for (i = 0, max = right_ary.length - 1; i < max; i += 1) {
                        right_ary[i] = ary[k];
                        k += 1;
                    }
                    k = start_left;
                    for (i = 0, max = left_ary.length - 1; i < max; i += 1) {
                        left_ary[i]= ary[k];
                        k += 1;
                    }
                    right_ary[right_ary.length - 1] = Infinity;
                    left_ary[left_ary.length - 1] = Infinity;
                    for (k = start_left; k < stop_right; k += 1) {
                        if (left_ary[m] <= right_ary[n]) {
                            ary[k] = left_ary[m];
                            m += 1;
                        } else {
                            ary[k] = right_ary[n];
                            n += 1;
                        }
                    }
                };

            while (step < ary.length) {
                left= 0;
                right = step;
                while (right + step <= ary.length) {
                    merge_arrays(ary, left, left + step, right,
                                 right + step);
                    left = right + step;
                    right = left + step;
                }
                if (right < ary.length) {
                    merge_arrays(ary, left, left + step, right, ary.length);
                }
                step *= 2;
            }
        };
        inner(this.data_store);
    }
};

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

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

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

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

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

console.log('Merge sort');
nums.setData();
start = new Date().getTime();
nums.merge_sort();
stop = new Date().getTime();
console.log('The elapsed time was: ' + (stop - start) + ' millseconds.');

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample3.js

sample3.js
 #1 Use the array literal notation [].
    var right_ary = new Array(stop_right - start_right + 1), // Line 164, Pos 46
 #2 Use the array literal notation [].
    left_ary = new Array(stop_left - start_left + 1), // Line 165, Pos 45
$ node sample3.js
Bubble sort
The elapsed time was: 1848 millseconds.
Selection sort
The elapsed time was: 418 millseconds.
Insertion sort
The elapsed time was: 382 millseconds.
Shell sort
The elapsed time was: 99 millseconds.
Merge sort
The elapsed time was: 22 millseconds.
$ node sample3.js
Bubble sort
The elapsed time was: 1830 millseconds.
Selection sort
The elapsed time was: 421 millseconds.
Insertion sort
The elapsed time was: 386 millseconds.
Shell sort
The elapsed time was: 103 millseconds.
Merge sort
The elapsed time was: 21 millseconds.
$ 

0 コメント:

コメントを投稿