<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) {
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 = {};
}
}
function humanSort(arr) {
const len = arr.length;
for (let i = 0; i < len; i++) {
let subIndex = i;
while (arr[subIndex] > arr[subIndex + 1] && subIndex > -1) {
const curr = arr[subIndex];
arr[subIndex] = arr[subIndex + 1];
arr[subIndex + 1] = curr;
subIndex--;
}
}
return arr;
}
</script>
var input = [];
for (var i = 0; i < 1000; i++) {
input[i] = Math.round(Math.random() * 1000000);
}
builtin_sort(input.slice(0));
naive_quicksort(input.slice(0));
inplace_quicksort(input.slice(0), 0, input.length);
heapSort(input.slice(0));
merge_sort(input.slice(0));
shell_sort(input.slice(0));
comb_sort(input.slice(0));
insertion_sort(input.slice(0));
fast_quicksort(input.slice(0));
mSort(input.slice(0));
radixBucketSort(input.slice(0))
bubbleSort(input.slice(0));
humanSort(input.slice(0));
--enable-precise-memory-info
flag.
Test case name | Result |
---|---|
Built-in Sort | |
Naive Quicksort | |
Inplace Quicksort | |
Heap Sort | |
Merge Sort | |
Shell Sort | |
Comb Sort | |
Insertion Sort | |
Fast QuickSort | |
mSort | |
Radix Bucket Sort | |
Bubble Sort | |
Human Sort |
Test name | Executions per second |
---|---|
Built-in Sort | 11947.8 Ops/sec |
Naive Quicksort | 1501.8 Ops/sec |
Inplace Quicksort | 6616.3 Ops/sec |
Heap Sort | 4411.4 Ops/sec |
Merge Sort | 2165.5 Ops/sec |
Shell Sort | 5665.4 Ops/sec |
Comb Sort | 2546.3 Ops/sec |
Insertion Sort | 808.0 Ops/sec |
Fast QuickSort | 6807.6 Ops/sec |
mSort | 2468.9 Ops/sec |
Radix Bucket Sort | 2368.4 Ops/sec |
Bubble Sort | 260.4 Ops/sec |
Human Sort | 70.8 Ops/sec |
It seems like you're ready to dive into the data!
Since I don't see any explicit questions or prompts in your message, I'll assume you'd like me to analyze and extract insights from the provided data. If you could provide more context or specific questions about the data, I'd be happy to help.
Assuming there's no question, here are some observations I can make:
Please provide more context or ask specific questions about the data if you'd like me to dig deeper!