Preparation Code Preparation HTML (this will be inserted in the <body>
of a valid HTML5 document in standards mode) (useful when testing DOM operations or including libraries) <script >
function swap (ary, a, b ) {
var t = ary[a];
ary[a] = ary[b];
ary[b] = t;
}
function builtin_sort__func (a, b ) {return a - b;};
function builtin_sort (ary ) {
return ary.sort (builtin_sort__func);
}
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;
}
function insertion_sort (ary ) {
for (var i=1 ,l=ary.length ;i<l;i++) {
var value = ary[i];
for (var j=i - 1 ;j>=0 ;j--) {
if (ary[j] <= value)
break ;
ary[j+1 ] = ary[j];
}
ary[j+1 ] = value;
}
return ary;
}
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);
}
function inplace_quicksort_partition (ary, start, end, pivotIndex ) {
var i = start, j = end;
var pivot = ary[pivotIndex];
while (true ) {
while (ary[i] < pivot) {i++};
j--;
while (pivot < ary[j]) {j--};
if (!(i<j)) {
return i;
}
swap (ary,i,j);
i++;
}
}
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;
}
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 ;
}
}
}
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;
}
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;
}
function comb_sort (ary ) {
var gap = ary.length ;
while (true ) {
gap = newgap (gap);
var swapped = false ;
for (var i=0 ,l=ary.length ;i<l;i++) {
var j = i + gap;
if (ary[i] < ary[j]) {
swap (ary,i,j);
swapped = true ;
}
}
if (gap == 1 && !swapped)
break ;
}
return ary;
}
function newgap (gap ) {
gap = ((gap * 10 ) / 13 ) | 0 ;
if (gap == 9 || gap == 10 )
gap = 11 ;
if (gap < 1 )
gap = 1 ;
return gap;
}
function fast_quicksort (ary ) {
var stack = [];
var entry = [0 ,ary.length ,2 * Math .floor (Math .log (ary.length )/Math .log (2 ))];
stack.push (entry);
while (stack.length > 0 ) {
entry = stack.pop ();
var start = entry[0 ];
var end = entry[1 ];
var depth = entry[2 ];
if (depth == 0 ) {
ary = shell_sort_bound (ary,start,end);
continue ;
}
depth--;
var pivot = Math .round ((start + end) / 2 );
var pivotNewIndex = inplace_quicksort_partition (ary,start,end, pivot);
if (end - pivotNewIndex > 16 ) {
entry = [pivotNewIndex,end,depth];
stack.push (entry);
}
if (pivotNewIndex - start > 16 ) {
entry = [start,pivotNewIndex,depth];
stack.push (entry);
}
}
ary = insertion_sort (ary);
return ary;
}
function shell_sort_bound (ary,start,end ) {
var inc = Math .round ((start + end)/2 ),
i, j, t;
while (inc >= start) {
for (i = inc; i < end; 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 JS var input = [];
for (var i = 0 ; i < 1000 ; i++) {
input[i] = Math .round (Math .random () * 1000000 );
}
Teardown JS