You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
133 lines
4.1 KiB
133 lines
4.1 KiB
/**
|
|
*
|
|
*/
|
|
var BubbleSort = function() {
|
|
var _this = this;
|
|
|
|
this.ui = {
|
|
presort: function presort(arr) {
|
|
_this
|
|
.instruct(Itemgroup.background, 1, 0, 0, arr.length, Visualizer.bg0)
|
|
|
|
.instruct(Itemgroup.message, 0, 0, 1, `Comparisons: ${_this.comparisons}`)
|
|
.instruct(Itemgroup.message, 0, 0, 2, `Swaps: ${_this.swaps}`)
|
|
.instruct(Itemgroup.message, 0, 0, 3, ``)
|
|
.instruct(Itemgroup.message, 0, 0, 4, ``)
|
|
.instruct(Itemgroup.message, 0, 100, 5, `Starting sort.`)
|
|
},
|
|
|
|
//
|
|
midsort: function midsort(arr, i) {
|
|
_this
|
|
.instruct(Itemgroup.background, 1, 0, 0, arr.length, Visualizer.bg0)
|
|
.instruct(Itemgroup.background, 1, 0, i, i, Visualizer.bg1)
|
|
.instruct(Itemgroup.background, 1, 0, (i - 1), (i - 1), Visualizer.bg1)
|
|
|
|
.instruct(Itemgroup.message, 0, 0, 1, `Comparisons: ${_this.comparisons}`)
|
|
.instruct(Itemgroup.message, 0, 0, 3, `Comparing ${arr[i - 1]} and ${arr[i]}.`)
|
|
.instruct(Itemgroup.message, 0, 0, 4, ``)
|
|
.instruct(Itemgroup.message, 0, 100, 5, ``)
|
|
},
|
|
|
|
//
|
|
swap: function swap(arr, i) {
|
|
_this
|
|
.instruct(Itemgroup.background, 1, 0, 0, arr.length, Visualizer.bg0)
|
|
.instruct(Itemgroup.background, 1, 0, i, i, Visualizer.bg1)
|
|
.instruct(Itemgroup.background, 1, 0, (i - 1), (i - 1), Visualizer.bg1)
|
|
|
|
.instruct(Itemgroup.message, 0, 0, 2, `Swaps: ${_this.swaps}`)
|
|
.instruct(Itemgroup.message, 0, 0, 4, `${arr[i]} > ${arr[i - 1]}`)
|
|
.instruct(Itemgroup.message, 0, 0, 5, `Swap current and previous.`)
|
|
.instruct(Itemgroup.swap, 1, 300, i, i - 1)
|
|
},
|
|
|
|
//
|
|
foundSwapped: function foundSwapped(arr) {
|
|
_this
|
|
.instruct(Itemgroup.background, 1, 0, 0, arr.length, Visualizer.bg0)
|
|
|
|
.instruct(Itemgroup.message, 0, 0, 3, ``)
|
|
.instruct(Itemgroup.message, 0, 0, 4, `Swapped elements found.`)
|
|
.instruct(Itemgroup.message, 0, 100, 5, `Recursing.`)
|
|
},
|
|
|
|
//
|
|
postsort: function postsort(arr) {
|
|
_this
|
|
.instruct(Itemgroup.background, 1, 0, 0, arr.length, Visualizer.bg0)
|
|
|
|
.instruct(Itemgroup.message, 0, 0, 1, `Comparisons: ${_this.comparisons}`)
|
|
.instruct(Itemgroup.message, 0, 0, 2, `Swaps: ${_this.swaps}`)
|
|
.instruct(Itemgroup.message, 0, 0, 3, ``)
|
|
.instruct(Itemgroup.message, 0, 0, 4, ``)
|
|
.instruct(Itemgroup.message, 0, 100, 5, `Sorting complete.`)
|
|
},
|
|
};
|
|
};
|
|
|
|
BubbleSort.prototype = Object.create(Sorter.prototype);
|
|
|
|
/**
|
|
*
|
|
*/
|
|
BubbleSort.prototype.init = function() {
|
|
var len = this.shuffled.length;
|
|
|
|
this.actions = [];
|
|
this.swaps = 0;
|
|
this.comparisons = 0;
|
|
|
|
this
|
|
.instruct(Itemgroup.items, 0, 0, len)
|
|
.instruct(Itemgroup.items, 1, 0, len)
|
|
.instruct(Itemgroup.items, 2, 0, len)
|
|
|
|
for (var i = 0; i < len; i++) {
|
|
this.instruct(Itemgroup.text, 1, 0, i, this.shuffled[i]);
|
|
}
|
|
|
|
this
|
|
.instruct(Itemgroup.foreground, 1, 0, 0, len, Visualizer.fg0)
|
|
.instruct(Itemgroup.background, 1, 0, 0, len, Visualizer.bg0)
|
|
|
|
.instruct(Itemgroup.opacity, 0, 0, 0, len, 0)
|
|
.instruct(Itemgroup.opacity, 2, 0, 0, len, 0)
|
|
};
|
|
|
|
/**
|
|
*
|
|
*/
|
|
BubbleSort.prototype.sort = function(arr) {
|
|
var i, tmp;
|
|
var swapped = false;
|
|
var len = arr.length;
|
|
|
|
this.ui.presort(arr);
|
|
|
|
for (i = 1; i < len; i++) {
|
|
this.comparisons++;
|
|
this.ui.midsort(arr, i);
|
|
|
|
if (arr[i - 1] > arr[i]) {
|
|
this.swaps++;
|
|
|
|
tmp = arr[i];
|
|
arr[i] = arr[i - 1];
|
|
arr[i - 1] = tmp;
|
|
|
|
swapped = true;
|
|
|
|
this.ui.swap(arr, i, i - 1);
|
|
}
|
|
}
|
|
|
|
if (swapped === true) {
|
|
this.ui.foundSwapped(arr);
|
|
this.sort(arr);
|
|
}
|
|
|
|
this.ui.postsort(arr);
|
|
|
|
return arr;
|
|
};
|
|
|