Benchmark for sorting algorithms ([Bubble, Selection, Insertion, Quick, Merge, Heap] Sort)

output.txt

----------------------------------------QUICK SORT----------------------------------------
[
    1,   3,   4,   4,   5,   5,   5,   6,   7,   7,   8,   9,
    9,  14,  15,  15,  15,  17,  18,  20,  22,  26,  27,  28,
   31,  33,  35,  35,  36,  36,  37,  38,  38,  40,  43,  45,
   45,  48,  50,  53,  53,  53,  53,  55,  56,  57,  57,  58,
   59,  59,  61,  64,  65,  66,  68,  69,  69,  71,  71,  73,
   74,  76,  77,  79,  82,  83,  83,  85,  85,  85,  88,  89,
   91,  93,  94,  95,  96,  97,  97,  98,  99,  99, 101, 102,
  103, 105, 106, 107, 107, 109, 109, 109, 110, 110, 111, 113,
  114, 117, 118, 119,
  ... 400 more items
]
for QUICK SORT, it took: 6ms
------------------------------------------------------------------------------------------
----------------------------------------MERGE SORT----------------------------------------
[
    1,   3,   4,   4,   5,   5,   5,   6,   7,   7,   8,   9,
    9,  14,  15,  15,  15,  17,  18,  20,  22,  26,  27,  28,
   31,  33,  35,  35,  36,  36,  37,  38,  38,  40,  43,  45,
   45,  48,  50,  53,  53,  53,  53,  55,  56,  57,  57,  58,
   59,  59,  61,  64,  65,  66,  68,  69,  69,  71,  71,  73,
   74,  76,  77,  79,  82,  83,  83,  85,  85,  85,  88,  89,
   91,  93,  94,  95,  96,  97,  97,  98,  99,  99, 101, 102,
  103, 105, 106, 107, 107, 109, 109, 109, 110, 110, 111, 113,
  114, 117, 118, 119,
  ... 400 more items
]
for MERGE SORT, it took: 4ms
------------------------------------------------------------------------------------------
----------------------------------------SELECTION SORT----------------------------------------
[
    1,   3,   4,   4,   5,   5,   5,   6,   7,   7,   8,   9,
    9,  14,  15,  15,  15,  17,  18,  20,  22,  26,  27,  28,
   31,  33,  35,  35,  36,  36,  37,  38,  38,  40,  43,  45,
   45,  48,  50,  53,  53,  53,  53,  55,  56,  57,  57,  58,
   59,  59,  61,  64,  65,  66,  68,  69,  69,  71,  71,  73,
   74,  76,  77,  79,  82,  83,  83,  85,  85,  85,  88,  89,
   91,  93,  94,  95,  96,  97,  97,  98,  99,  99, 101, 102,
  103, 105, 106, 107, 107, 109, 109, 109, 110, 110, 111, 113,
  114, 117, 118, 119,
  ... 400 more items
]
for SELECTION SORT, it took: 11ms
----------------------------------------------------------------------------------------------
----------------------------------------INSERTION SORT----------------------------------------
[
    1,   3,   4,   4,   5,   5,   5,   6,   7,   7,   8,   9,
    9,  14,  15,  15,  15,  17,  18,  20,  22,  26,  27,  28,
   31,  33,  35,  35,  36,  36,  37,  38,  38,  40,  43,  45,
   45,  48,  50,  53,  53,  53,  53,  55,  56,  57,  57,  58,
   59,  59,  61,  64,  65,  66,  68,  69,  69,  71,  71,  73,
   74,  76,  77,  79,  82,  83,  83,  85,  85,  85,  88,  89,
   91,  93,  94,  95,  96,  97,  97,  98,  99,  99, 101, 102,
  103, 105, 106, 107, 107, 109, 109, 109, 110, 110, 111, 113,
  114, 117, 118, 119,
  ... 400 more items
]
for INSERTION SORT, it took: 6ms
----------------------------------------------------------------------------------------------
----------------------------------------BUBBLE SORT----------------------------------------
[
    1,   3,   4,   4,   5,   5,   5,   6,   7,   7,   8,   9,
    9,  14,  15,  15,  15,  17,  18,  20,  22,  26,  27,  28,
   31,  33,  35,  35,  36,  36,  37,  38,  38,  40,  43,  45,
   45,  48,  50,  53,  53,  53,  53,  55,  56,  57,  57,  58,
   59,  59,  61,  64,  65,  66,  68,  69,  69,  71,  71,  73,
   74,  76,  77,  79,  82,  83,  83,  85,  85,  85,  88,  89,
   91,  93,  94,  95,  96,  97,  97,  98,  99,  99, 101, 102,
  103, 105, 106, 107, 107, 109, 109, 109, 110, 110, 111, 113,
  114, 117, 118, 119,
  ... 400 more items
]
for BUBBLE SORT, it took: 15ms
-------------------------------------------------------------------------------------------
----------------------------------------HEAP SORT----------------------------------------
[
    1,   3,   4,   4,   5,   5,   5,   6,   7,   7,   8,   9,
    9,  14,  15,  15,  15,  17,  18,  20,  22,  26,  27,  28,
   31,  33,  35,  35,  36,  36,  37,  38,  38,  40,  43,  45,
   45,  48,  50,  53,  53,  53,  53,  55,  56,  57,  57,  58,
   59,  59,  61,  64,  65,  66,  68,  69,  69,  71,  71,  73,
   74,  76,  77,  79,  82,  83,  83,  85,  85,  85,  88,  89,
   91,  93,  94,  95,  96,  97,  97,  98,  99,  99, 101, 102,
  103, 105, 106, 107, 107, 109, 109, 109, 110, 110, 111, 113,
  114, 117, 118, 119,
  ... 400 more items
]
for HEAP SORT, it took: 8ms
-----------------------------------------------------------------------------------------

sorting-algorithm-benchmark.js

const BENCH_ARRAY = (function randomizeArray(n) {
    let result = [];

    while (result.length < n) {
        result.push(Math.floor(Math.random() * n + 1));
    }

    return result;
})(500);

// Quick sort
// -----------------------------------------------
/**
 * @function quickSort
 * @param {number[]} arr
 * @param {number} [low=0]
 * @param {number} [high=arr.length-1]
 * @returns {number[]}
 */
function quickSort(arr, low = 0, high = arr.length - 1) {
    if (arr.length > 1) {
        let index = partition(arr, low, high);

        if (low < index - 1) {
            quickSort(arr, low, index - 1);
        }

        if (high > index) {
            quickSort(arr, index, high);
        }
    }

    return arr;
}

function partition(arr, low, high) {
    let pivot = arr[Math.floor((low + high) / 2)],
        i = low,
        j = high;

    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }

        while (arr[j] > pivot) {
            j--;
        }

        if (i <= j) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            j--;
            i++;
        }
    }

    return i;
}

benchmarkAlgo(quickSort);

// Merge sort
// -----------------------------------------------
/**
 * @function mergeSort
 * @param {number[]} arr
 * @param {number} [N=arr.length]
 * @returns {number[]}
 */
function mergeSort(arr, N = arr.length) {
    if (N < 2) return arr;

    let mid = parseInt(N / 2),
        leftSubArray = mergeSort(arr.slice(0, mid)),
        rightSubArray = mergeSort(arr.slice(mid));

    return mergeArray(leftSubArray, rightSubArray);
}

/**
 * @function mergeArray
 * @param {number[]} left
 * @param {number[]} right
 * @return {number[]}
 */
function mergeArray(left, right) {
    const result = [];

    while (left.length && right.length) {
        result.push(left[0] < right[0] ? left.shift() : right.shift());
    }

    return result.concat(left.length ? left : right);
}

benchmarkAlgo(mergeSort);

// Selection sort
// -----------------------------------------------
/**
 * @function selectionSort
 * @param {number[]} arr
 * @param {number} [N=arr.length]
 */
function selectionSort(arr, N = arr.length) {
    let min;
    for (let i = 0; i < N; i++) {
        min = i;

        for (let j = i + 1; j < N; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }

        if (i != min) {
            [arr[i], arr[min]] = [arr[min], arr[i]];
        }
    }

    return arr;
}

benchmarkAlgo(selectionSort);

// Insertion sort
// -----------------------------------------------
function insertionSort(arr, N = arr.length) {
    let j, key, i;

    for (i = 1; i < N; i++) {
        j = i - 1;
        key = arr[i];

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }

    return arr;
}

benchmarkAlgo(insertionSort);

// Bubble sort
// -----------------------------------------------
function bubbleSort(arr, N = arr.length) {
    let swapped = true;
    while (swapped) {
        swapped = false;
        for (let i = 0; i < N; i++) {
            if (arr[i] > arr[i + 1]) {
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
    }

    return arr;
}

benchmarkAlgo(bubbleSort);

/**
 * @function heapSort
 * @param {number[]} arr Unsorted array input
 * @param {number} [N=arr.length] default array size
 */
function heapSort(arr, N = arr.length) {
    for (let i = Math.floor(N / 2) - 1; i >= 0; i--) heapify(arr, N, i);

    for (let i = N - 1; i > 0; i--) {
        [arr[i], arr[0]] = [arr[0], arr[i]];
        heapify(arr, i, 0);
    }

    return arr;
}

/**
 * @function heapify
 * @param {number} N Heap size
 * @param {number} rootIdx Root index of heap array
 */
function heapify(arr, N, rootIdx) {
    let largest = rootIdx,
        left = 2 * rootIdx + 1,
        right = 2 * rootIdx + 2;

    if (left < N && arr[left] > arr[largest]) largest = left;
    if (right < N && arr[right] > arr[largest]) largest = right;

    if (rootIdx != largest) {
        [arr[largest], arr[rootIdx]] = [arr[rootIdx], arr[largest]];
        heapify(arr, N, largest);
    }
}

benchmarkAlgo(heapSort);

function benchmarkAlgo(func) {
    console.log(getFunctionNameWithBoundaries(func.name));
    let start = performance.now();
    console.log(func([...BENCH_ARRAY]));
    let end = performance.now();
    console.log('for ' + getFunctionNameAsUpperCaseSpaceSeparated(func.name) + ', it took:', parseInt(end - start).toString() + 'ms');
    console.log(getFunctionNameWithBoundaries(func.name, false));
}

function getFunctionNameWithBoundaries(str, shouldPrintName = true, boundaries = 40) {
	str = getFunctionNameAsUpperCaseSpaceSeparated(str);
	return shouldPrintName ? "-".repeat(boundaries) + str + "-".repeat(boundaries) : "-".repeat((boundaries * 2) + str.length);
}

function getFunctionNameAsUpperCaseSpaceSeparated(str) {
	return str.split(/(?=[A-Z])/).map(c => c.toUpperCase()).join(` `);
}