開発環境
- 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 コメント:
コメントを投稿