Skip to content

Instantly share code, notes, and snippets.

@memolog
Last active August 19, 2018 08:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save memolog/9e9475a1b91770dd7b25d44904771fbb to your computer and use it in GitHub Desktop.
Save memolog/9e9475a1b91770dd7b25d44904771fbb to your computer and use it in GitHub Desktop.
function test(method, array, showArray){
let arrayLength;
if (typeof array === 'number') {
arrayLength = array;
array = [];
for (let i=0; i<arrayLength; i++) {
array.push(Math.floor(Math.random()*10000));
}
} else {
arrayLength = array.length;
}
const methods = method instanceof Array ? method : method.split(',');
methods.forEach((m)=>{
const arrayCloned = [].concat(array);
console.log(`---- ${m.name || m} ----`);
if (showArray) {
console.log(arrayCloned);
}
console.time('sorting');
m = typeof m === 'string' ? eval(m) : m;
eval(m)(arrayCloned, showArray);
console.timeEnd('sorting');
});
}
function bubbleSort(array, showArray) {
let count = 0;
const arrayLength = array.length;
let swapped;
for (let i=arrayLength; i>0; i--) {
swapped = 0;
for ( let j=1; j<i; j++ ) {
const a = array[j-1];
const b = array[j];
if (a > b) {
array[j-1] = b;
array[j] = a;
swapped = j;
}
count++;
}
if (!swapped) {
break;
} else {
i = swapped + 1;
}
if (showArray) {
console.log(array);
}
}
console.log(`number of iterates: ${count}`);
}
function selectionSort(array, showArray) {
let count = 0;
const arrayLength = array.length;
for (let j=0; j<arrayLength - 1; j++) {
let minIndex = j;
for (let i=j+1; i<arrayLength; i++) {
if (array[i] < array[minIndex]) {
minIndex = i;
}
count++;
}
if (j !== minIndex) {
const temp = array[j];
array[j] = array[minIndex];
array[minIndex] = temp;
}
if (showArray) {
console.log(array);
}
}
console.log(`number of iterates: ${count}`);
}
function insertionSort(array, showArray) {
let count = 0;
const arrayLength = array.length;
for (let i=1; i<arrayLength; i++) {
const a = array[i];
let j = i-1;
for (; j>=0; j--) {
count++;
const b = array[j];
if (a < b) {
array[j+1] = b
} else {
break;
}
}
array[j+1] = a;
if (showArray) {
console.log(array);
}
}
console.log(`number of iterates: ${count}`);
}
function topDownMerge(sourceArray, begin, middle, end, resultArray, showArray, count) {
let i = begin;
let j = middle;
for (let k = begin; k < end; k++) {
if (i < middle && (j >= end || sourceArray[i] <= sourceArray[j])) {
resultArray[k] = sourceArray[i];
i = i + 1;
} else {
resultArray[k] = sourceArray[j];
j = j + 1;
}
count.count++;
}
if (showArray) {
console.log(resultArray);
}
}
function topDownSplitMerge(sourceArray, begin, end, sortingArray, showArray, count) {
const length = end - begin;
if (length < 2) {
return;
}
const middle = Math.floor((end + begin) / 2);
topDownSplitMerge(sortingArray, begin, middle, sourceArray, showArray, count);
topDownSplitMerge(sortingArray, middle, end, sourceArray, showArray, count);
topDownMerge(sourceArray, begin, middle, end, sortingArray, showArray, count);
}
function topDownMergeSort(array, showArray) {
const count = {
count: 0
};
const workingArray = array.slice(); // copy array
topDownSplitMerge(workingArray, 0, array.length, array, showArray, count);
if (showArray) {
console.log(array);
}
console.log(`number of iterates: ${count.count}`);
}
const argv = process.argv;
test(argv[2], parseInt(argv[3], 10), argv[4]);
@memolog
Copy link
Author

memolog commented Aug 4, 2018

> test(bubbleSort, 10000)
number of iterate: 49945789
sorting: 224.716ms

> test(bubbleSort, 10000)
number of iterate: 49953813
sorting: 186.189ms

> test(selectionSort, 10000)
number of iterate: 49995000
sorting: 118.827ms

> test(selectionSort, 10000)
number of iterate: 49995000
sorting: 118.816ms

@memolog
Copy link
Author

memolog commented Aug 4, 2018

> test(bubbleSort, 10, true)
[ 9119, 5342, 7436, 6114, 9021, 9137, 970, 7143, 4550, 8967 ]
[ 5342, 7436, 6114, 9021, 9119, 970, 7143, 4550, 8967, 9137 ]
[ 5342, 6114, 7436, 9021, 970, 7143, 4550, 8967, 9119, 9137 ]
[ 5342, 6114, 7436, 970, 7143, 4550, 8967, 9021, 9119, 9137 ]
[ 5342, 6114, 970, 7143, 4550, 7436, 8967, 9021, 9119, 9137 ]
[ 5342, 970, 6114, 4550, 7143, 7436, 8967, 9021, 9119, 9137 ]
[ 970, 5342, 4550, 6114, 7143, 7436, 8967, 9021, 9119, 9137 ]
[ 970, 4550, 5342, 6114, 7143, 7436, 8967, 9021, 9119, 9137 ]
number of iterate: 40
sorting: 0.224ms

> test(bubbleSort, 10, true)
[ 1954, 1674, 3550, 8909, 3023, 2472, 3475, 4214, 1468, 4807 ]
[ 1674, 1954, 3550, 3023, 2472, 3475, 4214, 1468, 4807, 8909 ]
[ 1674, 1954, 3023, 2472, 3475, 3550, 1468, 4214, 4807, 8909 ]
[ 1674, 1954, 2472, 3023, 3475, 1468, 3550, 4214, 4807, 8909 ]
[ 1674, 1954, 2472, 3023, 1468, 3475, 3550, 4214, 4807, 8909 ]
[ 1674, 1954, 2472, 1468, 3023, 3475, 3550, 4214, 4807, 8909 ]
[ 1674, 1954, 1468, 2472, 3023, 3475, 3550, 4214, 4807, 8909 ]
[ 1674, 1468, 1954, 2472, 3023, 3475, 3550, 4214, 4807, 8909 ]
[ 1468, 1674, 1954, 2472, 3023, 3475, 3550, 4214, 4807, 8909 ]
number of iterate: 38
sorting: 0.223ms

> test(selectionSort, 10, true)
[ 9897, 3616, 4291, 3463, 6015, 3022, 9464, 2056, 3939, 3419 ]
[ 2056, 3616, 4291, 3463, 6015, 3022, 9464, 9897, 3939, 3419 ]
[ 2056, 3022, 4291, 3463, 6015, 3616, 9464, 9897, 3939, 3419 ]
[ 2056, 3022, 3419, 3463, 6015, 3616, 9464, 9897, 3939, 4291 ]
[ 2056, 3022, 3419, 3463, 6015, 3616, 9464, 9897, 3939, 4291 ]
[ 2056, 3022, 3419, 3463, 3616, 6015, 9464, 9897, 3939, 4291 ]
[ 2056, 3022, 3419, 3463, 3616, 3939, 9464, 9897, 6015, 4291 ]
[ 2056, 3022, 3419, 3463, 3616, 3939, 4291, 9897, 6015, 9464 ]
[ 2056, 3022, 3419, 3463, 3616, 3939, 4291, 6015, 9897, 9464 ]
[ 2056, 3022, 3419, 3463, 3616, 3939, 4291, 6015, 9464, 9897 ]
number of iterate: 45
sorting: 0.280ms

> test(selectionSort, 10, true)
[ 658, 6553, 7076, 9879, 8176, 2923, 3082, 4011, 2146, 6253 ]
[ 658, 6553, 7076, 9879, 8176, 2923, 3082, 4011, 2146, 6253 ]
[ 658, 2146, 7076, 9879, 8176, 2923, 3082, 4011, 6553, 6253 ]
[ 658, 2146, 2923, 9879, 8176, 7076, 3082, 4011, 6553, 6253 ]
[ 658, 2146, 2923, 3082, 8176, 7076, 9879, 4011, 6553, 6253 ]
[ 658, 2146, 2923, 3082, 4011, 7076, 9879, 8176, 6553, 6253 ]
[ 658, 2146, 2923, 3082, 4011, 6253, 9879, 8176, 6553, 7076 ]
[ 658, 2146, 2923, 3082, 4011, 6253, 6553, 8176, 9879, 7076 ]
[ 658, 2146, 2923, 3082, 4011, 6253, 6553, 7076, 9879, 8176 ]
[ 658, 2146, 2923, 3082, 4011, 6253, 6553, 7076, 8176, 9879 ]
number of iterate: 45
sorting: 0.239ms

@memolog
Copy link
Author

memolog commented Aug 7, 2018

> test(insertionSort, 10, true);
[ 5520, 4913, 1859, 4810, 9119, 5459, 4763, 5446, 2098, 7777 ]
[ 4913, 5520, 1859, 4810, 9119, 5459, 4763, 5446, 2098, 7777 ]
[ 1859, 4913, 5520, 4810, 9119, 5459, 4763, 5446, 2098, 7777 ]
[ 1859, 4810, 4913, 5520, 9119, 5459, 4763, 5446, 2098, 7777 ]
[ 1859, 4810, 4913, 5520, 9119, 5459, 4763, 5446, 2098, 7777 ]
[ 1859, 4810, 4913, 5459, 5520, 9119, 4763, 5446, 2098, 7777 ]
[ 1859, 4763, 4810, 4913, 5459, 5520, 9119, 5446, 2098, 7777 ]
[ 1859, 4763, 4810, 4913, 5446, 5459, 5520, 9119, 2098, 7777 ]
[ 1859, 2098, 4763, 4810, 4913, 5446, 5459, 5520, 9119, 7777 ]
[ 1859, 2098, 4763, 4810, 4913, 5446, 5459, 5520, 7777, 9119 ]
number of iterates: 30
sorting: 0.705ms

> test(insertionSort, 10, true);
[ 1794, 4601, 6273, 3605, 573, 673, 6637, 4949, 1867, 5156 ]
[ 1794, 4601, 6273, 3605, 573, 673, 6637, 4949, 1867, 5156 ]
[ 1794, 4601, 6273, 3605, 573, 673, 6637, 4949, 1867, 5156 ]
[ 1794, 3605, 4601, 6273, 573, 673, 6637, 4949, 1867, 5156 ]
[ 573, 1794, 3605, 4601, 6273, 673, 6637, 4949, 1867, 5156 ]
[ 573, 673, 1794, 3605, 4601, 6273, 6637, 4949, 1867, 5156 ]
[ 573, 673, 1794, 3605, 4601, 6273, 6637, 4949, 1867, 5156 ]
[ 573, 673, 1794, 3605, 4601, 4949, 6273, 6637, 1867, 5156 ]
[ 573, 673, 1794, 1867, 3605, 4601, 4949, 6273, 6637, 5156 ]
[ 573, 673, 1794, 1867, 3605, 4601, 4949, 5156, 6273, 6637 ]
number of iterates: 27
sorting: 0.471ms

> test(insertionSort, 10, true);
[ 8125, 1061, 9076, 19, 8703, 5125, 2306, 9347, 5543, 1661 ]
[ 1061, 8125, 9076, 19, 8703, 5125, 2306, 9347, 5543, 1661 ]
[ 1061, 8125, 9076, 19, 8703, 5125, 2306, 9347, 5543, 1661 ]
[ 19, 1061, 8125, 9076, 8703, 5125, 2306, 9347, 5543, 1661 ]
[ 19, 1061, 8125, 8703, 9076, 5125, 2306, 9347, 5543, 1661 ]
[ 19, 1061, 5125, 8125, 8703, 9076, 2306, 9347, 5543, 1661 ]
[ 19, 1061, 2306, 5125, 8125, 8703, 9076, 9347, 5543, 1661 ]
[ 19, 1061, 2306, 5125, 8125, 8703, 9076, 9347, 5543, 1661 ]
[ 19, 1061, 2306, 5125, 5543, 8125, 8703, 9076, 9347, 1661 ]
[ 19, 1061, 1661, 2306, 5125, 5543, 8125, 8703, 9076, 9347 ]
number of iterates: 30
sorting: 0.443ms

> test(insertionSort, 10000);
number of iterates: 25064166
sorting: 65.927ms

> test(insertionSort, 10000);
number of iterates: 25021144
sorting: 65.638ms

> test(insertionSort, 10000);
number of iterates: 24861736
sorting: 65.277ms

@memolog
Copy link
Author

memolog commented Aug 19, 2018

node sortTest.js bubbleSort,selectionSort,insertionSort,topDownMergeSort 10000
---- bubbleSort ----
number of iterates: 49909120
sorting: 230.373ms
---- selectionSort ----
number of iterates: 49995000
sorting: 134.691ms
---- insertionSort ----
number of iterates: 24925812
sorting: 61.047ms
---- topDownMergeSort ----
number of iterates: 133616
sorting: 6.362ms

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment