Created
May 7, 2023 10:02
-
-
Save 2bam/0d51158a865765e3c16ddcdc8b8ca525 to your computer and use it in GitHub Desktop.
JS sorting algorithm benchmarks [keeping it in case it's lost]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// Thx https://www.measurethat.net/Benchmarks/Show/3549/0/javascript-sorting-algorithms | |
// | |
// 1000x random ordered: https://www.measurethat.net/Benchmarks/Show/3549/0/javascript-sorting-algorithms | |
// 1000x almost ordered: https://www.measurethat.net/Benchmarks/Show/25092/0/javascript-sorting-algorithms-best-case-almost-ordered | |
// | |
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) { | |
return a - b; | |
}); | |
} | |
// 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; | |
} | |
//Insertion sort | |
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; | |
} | |
// 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 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; | |
} | |
// 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; | |
} | |
//Comb Sort (Basically bubblesort with a small modification, but heaps faster) | |
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; | |
} | |
//faster quicksort using a stack to eliminate recursion, sorting inplace to reduce memory usage, and using insertion sort for small partition sizes | |
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; | |
} | |
function mSort(list) { | |
if (list.length < 14) { | |
return insertion_sort(list); | |
} | |
var half = Math.floor(list.length / 2); | |
var a = mSort(list.slice(0, half)); | |
var b = mSort(list.slice(half, list.length)); | |
var aCount = 0; | |
var bCount = 0; | |
var returnList = []; | |
while (true) { | |
if (a[aCount] <= b[bCount]) { | |
returnList.push(a[aCount]); | |
aCount++; | |
if (aCount === a.length) { | |
returnList = returnList.concat(b.slice(bCount, b.length)); | |
break; | |
} | |
} | |
else { | |
returnList.push(b[bCount]); | |
bCount++; | |
if (bCount === b.length) { | |
returnList = returnList.concat(a.slice(aCount, a.length)); | |
break; | |
} | |
} | |
} | |
return returnList; | |
} | |
function bubbleSort(items) { | |
var length = items.length; | |
for (var i = 0; i < length; i++) { //Number of passes | |
for (var j = 0; j < (length - i - 1); j++) { //Notice that j < (length - i) | |
//Compare the adjacent positions | |
if(items[j] > items[j+1]) { | |
//Swap the numbers | |
var tmp = items[j]; //Temporary variable to hold the current number | |
items[j] = items[j+1]; //Replace current number with adjacent number | |
items[j+1] = tmp; //Replace adjacent number with current number | |
} | |
} | |
} | |
} | |
https://stackoverflow.com/a/38979903/8769328 | |
function radixBucketSort (arr) { | |
var idx1, idx2, idx3, len1, len2, radix, radixKey; | |
var radices = {}, buckets = {}, num, curr; | |
var currLen, radixStr, currBucket; | |
len1 = arr.length; | |
len2 = 10; // radix sort uses ten buckets | |
// find the relevant radices to process for efficiency | |
for (idx1 = 0;idx1 < len1;idx1++) { | |
radices[arr[idx1].toString().length] = 0; | |
} | |
// loop for each radix. For each radix we put all the items | |
// in buckets, and then pull them out of the buckets. | |
for (radix in radices) { | |
// put each array item in a bucket based on its radix value | |
len1 = arr.length; | |
for (idx1 = 0;idx1 < len1;idx1++) { | |
curr = arr[idx1]; | |
// item length is used to find its current radix value | |
currLen = curr.toString().length; | |
// only put the item in a radix bucket if the item | |
// key is as long as the radix | |
if (currLen >= radix) { | |
// radix starts from beginning of key, so need to | |
// adjust to get redix values from start of stringified key | |
radixKey = curr.toString()[currLen - radix]; | |
// create the bucket if it does not already exist | |
if (!buckets.hasOwnProperty(radixKey)) { | |
buckets[radixKey] = []; | |
} | |
// put the array value in the bucket | |
buckets[radixKey].push(curr); | |
} else { | |
if (!buckets.hasOwnProperty('0')) { | |
buckets['0'] = []; | |
} | |
buckets['0'].push(curr); | |
} | |
} | |
// for current radix, items are in buckets, now put them | |
// back in the array based on their buckets | |
// this index moves us through the array as we insert items | |
idx1 = 0; | |
// go through all the buckets | |
for (idx2 = 0;idx2 < len2;idx2++) { | |
// only process buckets with items | |
if (buckets[idx2] != null) { | |
currBucket = buckets[idx2]; | |
// insert all bucket items into array | |
len1 = currBucket.length; | |
for (idx3 = 0;idx3 < len1;idx3++) { | |
arr[idx1++] = currBucket[idx3]; | |
} | |
} | |
} | |
buckets = {}; | |
} | |
} | |
var input = []; | |
for (var i = 0; i < 1000; i++) { | |
input[i] = Math.round(Math.random() * 1000000); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Chrome 112 - i7-6700HQ Skylake - Windows 10.
For 1000x random numbers
For 1000 almost ordered (10 out of order)