This repository has been archived on 2020-05-03. You can view files and clone it, but cannot push or open issues or pull requests.
sorts/dist-archive/sorts-combined.htm

291 lines
6.1 KiB
HTML
Raw Permalink Normal View History

2012-05-08 00:00:00 +00:00
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<script>
"use strict";
var TIMEOUT = 16;
var EL_COUNT = 100;
window.onload = function() {
display.build(EL_COUNT, document.body);
};
//
// Infrastructure
//
var display = {
highlighted: false,
build: function(size, parent_id) {
var parent = document.getElementById(parent_id);
parent.style.position = 'relative';
parent.style.display = 'block';
parent.style.width = (10 * size)+'px';
parent.style.height = (3 * size)+'px';
for (var i = 0; i < size; i++) {
var d = document.createElement('div');
d.style.position = 'absolute';
d.style.display = 'block';
d.style['background-color'] = 'green';
d.style.width = '10px';
d.style.left = (10 * i)+'px';
d.id = 'el-'+i;
parent.appendChild(d);
this.set(i, i);
}
EL_COUNT = size;
this.clear_highlight();
},
set: function(idx, val) {
var el = document.getElementById('el-'+idx);
if (! el) {
console.log("Invalid set " + idx);
return;
}
el.style.height = (val * 3) + 'px';
el.style.top = ((EL_COUNT - val) * 3) + 'px';
this.highlight(idx);
},
get: function(idx) {
var el = document.getElementById('el-'+idx);
if (! el) {
console.log("Invalid read "+idx);
return;
}
return parseInt(el.style.height) / 3;
},
swap: function(a, b) {
var tmp = this.get(a);
this.set(a, this.get(b));
this.set(b, tmp);
},
reset: function() {
for (var i = 0; i < EL_COUNT; i++) this.set(i, i);
this.clear_highlight();
},
highlight: function(idx) {
this.clear_highlight();
document.getElementById('el-'+idx).
style['background-color'] = 'darkgreen';
this.highlighted = idx;
},
clear_highlight: function(idx) {
if (this.highlighted === false) return;
document.getElementById('el-'+this.highlighted).
style['background-color'] = 'green';
this.highlighted = false;
}
};
var Set = function() {
this.moves = [];
this.items = [];
for (var i = 0; i < EL_COUNT; i++) {
this.items.push( display.get(i) );
}
};
Set.prototype.get = function(idx) {
return this.items[idx];
}
Set.prototype.swap = function(a, b) {
this.moves.push([a, b]);
var tmp = this.items[a];
this.items[a] = this.items[b];
this.items[b] = tmp;
}
Set.prototype.apply = function() {
for (var i = 0, e = this.moves.length; i < e; i++) {
display.swap(this.moves[i][0], this.moves[i][1]);
}
this.moves = [];
display.clear_highlight();
}
Set.prototype.animate = function() {
if (this.moves.length) {
display.swap(this.moves[0][0], this.moves[0][1]);
this.moves = this.moves.slice(1);
setTimeout(this.animate.bind(this), TIMEOUT);
} else {
display.clear_highlight();
}
}
//
// Sorts
//
var doPermute = function() {
var s = new Set();
for (var i = 0; i < EL_COUNT; i++) {
s.swap(Math.floor(Math.random()*EL_COUNT), i);
}
return s;
}
var doPerturb = function() {
var s = new Set();
for (var i = 5; i < EL_COUNT - 5; i++) {
s.swap(i, Math.floor(Math.random()*10)+i-5);
}
return s;
}
var doReverse = function() {
var s = new Set();
for (var i = 0; i < EL_COUNT/2; i++) {
s.swap(i, EL_COUNT-i-1);
}
return s;
}
var doBubble = function() {
// Outline: Wikipedia
var s = new Set();
var n = EL_COUNT;
do {
var new_n = 0;
for (var i = 1; i < n; i++) {
if (s.get(i-1) > s.get(i)) {
s.swap(i-1, i);
new_n = i;
}
}
n = new_n;
} while(n);
return s;
}
var doQuick = function() {
// Outline: Wikipedia
var partition = function(set, left, right, pivot) {
var pval = set.get(pivot);
set.swap(pivot, right);
var store_idx = left;
for (var i = left; i < right; i++) {
if (set.get(i) < pval) {
set.swap(i, store_idx);
store_idx++;
}
}
set.swap(store_idx, right);
return store_idx;
};
var qsort = function(set, left, right) {
if (left < right) {
var pivot_idx = Math.floor((right - left)/2) + left;
var pivot_new = partition(set, left, right, pivot_idx);
qsort(set, left, pivot_new-1);
qsort(set, pivot_new+1, right);
}
};
var s = new Set();
qsort(s, 0, s.items.length - 1);
return s;
}
var doHeap = function() {
// Outline: Wikipedia
var heapify = function(s, count) {
var start = (count-2) / 2;
while (start >= 0) {
siftdown(s, start, count-1);
start--;
}
};
var siftdown = function(s, start, end) {
var root = start;
while (root*2 < end) {
var child = root*2 + 1;
var swap = root;
if (s.get(swap) < s.get(child)) {
swap = child;
}
if (child+1 <= end && s.get(swap) < s.get(child+1)) {
swap = child + 1;
}
if (swap != root) {
s.swap(root, swap);
root = swap;
} else {
return;
}
};
};
var s = new Set();
heapify(s, s.items.length);
var end = s.items.length - 1;
while (end) {
s.swap(end, 0);
end--;
siftdown(s, 0, end);
}
return s;
}
var doMerge = function() {
// Outline: http://www.cs.ubc.ca/~harrison/Java/MergeSortAlgorithm.java.html
var msort = function(s, lo, hi) {
if (lo >= hi) return;
var mid = Math.floor((lo + hi) / 2);
msort(s, lo, mid);
msort(s, mid+1, hi);
var end_lo = mid;
var start_hi = mid+1;
while ((lo <= end_lo) && (start_hi <= hi)) {
if (s.get(lo) < s.get(start_hi)) {
lo++;
} else {
for (var k = start_hi - 1; k >= lo; k--) {
s.swap(k+1, k);
}
end_lo++;
start_hi++;
}
}
}
var s = new Set();
msort(s, 0, s.items.length - 1);
return s;
}
</script>
<title>sorts</title>
</head>
<body onload="display.build(100, 'area');">
<div id="area"></div>
<a href="javascript:display.reset()">reset</a>
|
<a href="javascript:doPermute().animate()">permute</a>
<a href="javascript:doPerturb().animate()">perturb</a>
<a href="javascript:doReverse().animate()">reverse</a>
|
<a href="javascript:doBubble().animate()">bubble</a>
<a href="javascript:doQuick().animate()">quick</a>
<a href="javascript:doHeap().animate()">heap</a>
<a href="javascript:doMerge().animate()">merge</a>
</body>
</html>