Skip to content

Instantly share code, notes, and snippets.

@lobodin
Created October 15, 2010 15:50
Show Gist options
  • Save lobodin/628421 to your computer and use it in GitHub Desktop.
Save lobodin/628421 to your computer and use it in GitHub Desktop.
/* Written using http://en.wikipedia.org/wiki/Heapsort pseudocode */
function Sorter() {
var array;
this.heapsort = function(a) {
array = a;
heapify();
var end = array.length - 1;
while (end > 0) {
swapElementsWithIndexes(end, 0);
siftDown(0, end - 1);
--end;
}
}
var heapify = function() {
for (var v = Math.floor(array.length / 2); v >= 0; v--) {
siftDown(v, array.length - 1);
}
}
var siftDown = function(start, end) {
var root = start;
while (root * 2 <= end) {
var child = root * 2;
if (child < end && array[child] < array[child+1]) {
++child;
}
if (array[root] >= array[child]) {
return;
}
swapElementsWithIndexes(root, child);
root = child;
}
}
var swapElementsWithIndexes = function(i, j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Heapsort</title>
<script type="text/javascript" src="heapsort.js"></script>
<script type="text/javascript">
function sortArray() {
var array = [];
for (var i = 0; i < 100; i++) {
array[i] = Math.floor(Math.random() * 1000);
}
var sorter = new Sorter();
sorter.heapsort(array);
var result = "<p>";
for (var i in array) {
result += array[i] + "<br>";
}
result += "</p>";
document.write(result);
}
</script>
</head>
<body onload="sortArray()">
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment