Sorting Algorithms (v11)

Preparation HTML

<script>
function swap(ary, a, b) {
var t = ary[a];
ary[a] = ary[b];
ary[b] = t;
}

// Built-in with comparison function (default sorting is "dictionary-style")
function builtin_sort(ary) {
return ary.sort(function(a, b) {
if (a === b) {
return 0;
}

return (a < b) ? -1 : 1;
});
}

// Bubble Sort
function bubble_sort(ary) {
var a, b;
for (a = 0; a < ary.length; a++) {
for (b = a + 1; b < ary.length; b++) {
if (ary[a] > ary[b]) {
swap(ary, a, b);
}
}
}

return ary;
}

// Naive (but understandable) quicksort (memory hog)
function naive_quicksort(ary) {
if (ary.length <= 1) {
return ary;
}

var less = [],
greater = [],
pivot = ary.pop();

for (var i = 0; i < ary.length; i++) {
if (ary[i] < pivot) {
less.push(ary[i]);
} else {
greater.push(ary[i]);
}
}

less = naive_quicksort(less);
greater = naive_quicksort(greater);

return less.concat(pivot, greater);
}

// In place quicksort
function inplace_quicksort_partition(ary, start, end, pivotIndex) {
var pivotValue = ary[pivotIndex],
storeIndex = start,
i;

swap(ary, pivotIndex, end - 1);

for (i = start; i < end - 1; i++) {
if (ary[i] < pivotValue) {
swap(ary, i, storeIndex);

storeIndex++;
}
}

swap(ary, storeIndex, end - 1);

return storeIndex;
}

function inplace_quicksort(ary, start, end) {
if (start < end - 1) {
var pivotIndex = Math.round((start + end) / 2);

pivotIndex = inplace_quicksort_partition(ary, start, end, pivotIndex);

inplace_quicksort(ary, start, pivotIndex - 1);
inplace_quicksort(ary, pivotIndex + 1, end);
}

return ary;
}

// Heap sort
function heapSort(ary) {
heapify(ary);

for (var end = ary.length - 1; end > 0; end--) {
swap(ary, end, 0);
shiftDown(ary, 0, end - 1);
}

return ary;
}

function heapify(ary) {
for (var start = (ary.length >> 1) - 1; start >= 0; start--) {
shiftDown(ary, start, ary.length - 1);
}
}

function shiftDown(ary, start, end) {
var root = start,
child, s;

while (root * 2 + 1 <= end) {
child = root * 2 + 1;
s = root;

if (ary[s] < ary[child]) {
s = child;
}

if (child + 1 <= end && ary[s] < ary[child + 1]) {
s = child + 1;
}

if (s !== root) {
swap(ary, root, s);
root = s;
} else {
return;
}
}
}

// Merge sort
function merge_sort(ary) {
if (ary.length <= 1) {
return ary;
}

var m = ary.length >> 1;

var left = ary.slice(0, m),
right = ary.slice(m);

return merge(merge_sort(left), merge_sort(right));
}

function merge(left, right) {
var result = [],
li = 0, ri = 0;

while (li < left.length || ri < right.length) {
if (li < left.length && ri < right.length) {
if (left[li] <= right[ri]) {
result.push(left[li]);
li++;
} else {
result.push(right[ri]);
ri++;
}
} else if (li < left.length) {
result.push(left[li]);
li++;
} else if (ri < right.length) {
result.push(right[ri]);
ri++;
}
}

return result;
}

// Shell sort
function shell_sort(ary) {
var inc = Math.round(ary.length / 2),
i, j, t;

while (inc > 0) {
for (i = inc; i < ary.length; i++) {
t = ary[i];
j = i;
while (j >= inc && ary[j - inc] > t) {
ary[j] = ary[j - inc];
j -= inc;
}
ary[j] = t;
}
inc = Math.round(inc / 2.2);
}

return ary;
}
</script>

Setup

var input = [];
for (var i = 0; i < 1000; i++) {
input[i] = ''+Math.round(Math.random() * 1000000);
}

Test runner

Testing in
TestOps/sec
Built-in Sort
builtin_sort(input.slice(0));
Bubble Sort
bubble_sort(input.slice(0));
Naive Quicksort
naive_quicksort(input.slice(0));
Inplace Quicksort
inplace_quicksort(input.slice(0), 0, input.length);