some sort algorithms

sort.js

// The MIT License (MIT)

// Copyright (c) 2017 Oleksii Rudenko

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

const assert = require('assert');

/**
 * Simple bubble sort, O(n^2)
 */
function bubbleSort(data) {
  for (var i = 0; i < data.length; i++) {
    for (var j = 0; j < data.length; j++) {
      if (data[j - 1] > data[j]) {
        swap(data, j - 1, j);
      }
    }
  }
  return data;
}

// test
assert.deepEqual(bubbleSort([]), []);
assert.deepEqual(bubbleSort([2, 1]), [1, 2]);
assert.deepEqual(bubbleSort([1, 2, 6, 5]), [1, 2, 5, 6]);

/**
 * Simple bubble sort optimize, O(n^2)
 */
function bubbleSortOpt(data) {
  var n = data.length;
  do {
    var swapped = false;
    for (var i = 1; i < n; i++) {
      if (data[i - 1] > data[i]) {
        swap(data, i - 1, i);
        swapped = true;
      }
    }
    n--;
  } while (n > 0);
  return data;
}

//test
assert.deepEqual(bubbleSortOpt([]), []);
assert.deepEqual(bubbleSortOpt([2, 1]), [1, 2]);
assert.deepEqual(bubbleSortOpt([1, 2, 6, 5]), [1, 2, 5, 6]);

/**
 * Insertion sort, O(n^2)
 */
function insertionSort(data) {
  for (var i = 1; i < data.length; i++) {
    for (var j = i; j > 0 && data[j - 1] > data[j]; j--) {
      swap(data, j - 1, j);
    }
  }
  return data;
}

// test
assert.deepEqual(insertionSort([]), []);
assert.deepEqual(insertionSort([2, 1]), [1, 2]);
assert.deepEqual(insertionSort([1, 2, 6, 5]), [1, 2, 5, 6]);

/**
 * Merge-sort, O(n log(n))
 */
function mergeSort(data) {
  if (data.length <= 1) return data;
  var left = data.slice(0, data.length / 2);
  var right = data.slice(data.length / 2);
  var leftSorted = mergeSort(left);
  var rightSorted = mergeSort(right);
  return mergeSort_merge(leftSorted, rightSorted);
}

function mergeSort_merge(leftSorted, rightSorted) {
  var result = [];
  for (var i = 0, j = 0; i < leftSorted.length && j < rightSorted.length; ) {
    if (leftSorted[i] < rightSorted[j]) {
      result.push(leftSorted[i++]);
    } else {
      result.push(rightSorted[j++]);
    }
  }
  while (i < leftSorted.length) {
    result.push(leftSorted[i++]);
  }
  while (j < rightSorted.length) {
    result.push(rightSorted[j++]);
  }
  return result;
}

// test
assert.deepEqual(mergeSort([]), []);
assert.deepEqual(mergeSort([2, 1]), [1, 2]);
assert.deepEqual(mergeSort([1, 2, 6, 5]), [1, 2, 5, 6]);

/**
 * Selection sort, O(n^2)
 */
function selectonSort(data) {
  for (var i = 0; i < data.length - 1; i++) {
    var minI = i;
    for (var j = i + 1; j < data.length; j++) {
      if (data[j] < data[minI]) {
        minI = j;
      }
    }
    swap(data, i, minI);
  }
  return data;
}

// test
assert.deepEqual(selectonSort([]), []);
assert.deepEqual(selectonSort([2, 1]), [1, 2]);
assert.deepEqual(selectonSort([1, 2, 6, 5]), [1, 2, 5, 6]);
assert.deepEqual(selectonSort([7, 3, 0, 4, 1, 6, 5, 2]), [
  0,
  1,
  2,
  3,
  4,
  5,
  6,
  7,
]);
/**
 * heapsort O(n log(n))
 */

// helpers for complete binary tree
function iParent(i) {
  if (i == 0) return 0;
  return Math.floor((i - 1) / 2);
}

function iLeftChild(i) {
  return 2 * i + 1;
}

function iRightChild(i) {
  return 2 * i + 2;
}

function heapify(data, count) {
  var start = iParent(count - 1);
  while (start >= 0) {
    siftDown(data, start, count - 1);
    start--;
  }
  return data;
}

function siftDown(data, start, end) {
  var root = start;
  while (iLeftChild(root) <= end) {
    var child = iLeftChild(root);
    var _swap = root;
    if (data[_swap] < data[child]) {
      _swap = child;
    }
    if (child + 1 <= end && data[_swap] < data[child + 1]) {
      _swap = child + 1;
    }
    if (_swap === root) {
      return;
    } else {
      swap(data, root, _swap);
      root = _swap;
    }
  }
  return data;
}

assert.deepEqual(heapify([2, 3, 1, 4, 5, 6], 6), [6, 5, 2, 4, 3, 1]);

/**
 * heapsort O(n log(n))
 */
function heapsort(data) {
  var count = data.length;
  heapify(data, count);
  var end = count - 1;
  while (end > 0) {
    swap(data, end, 0);
    end = end - 1;
    siftDown(data, 0, end);
  }
  return data;
}

// test
assert.deepEqual(heapsort([]), []);
assert.deepEqual(heapsort([2, 1]), [1, 2]);
assert.deepEqual(heapsort([1, 2, 6, 5]), [1, 2, 5, 6]);
assert.deepEqual(heapsort([1, 3, 3, 8, 10, 2, 6, 5]), [
  1,
  2,
  3,
  3,
  5,
  6,
  8,
  10,
]);

/**
 * quicksort, O(n^2) worst
 */

function quicksort(data) {
  _quicksort(data, 0, data.length - 1);
  return data;
}

function _quicksort(data, lo, hi) {
  if (lo < hi) {
    var p = _partition(data, lo, hi);
    _quicksort(data, lo, p);
    _quicksort(data, p + 1, hi);
  }
}

function _partition(data, lo, hi) {
  var pivot = data[lo];
  var i = lo - 1;
  var j = hi + 1;
  for (;;) {
    do {
      i++;
    } while (data[i] < pivot);
    do {
      j--;
    } while (data[j] > pivot);

    if (i >= j) {
      return j;
    }

    swap(data, i, j);
  }
}

// test
assert.deepEqual(quicksort([]), []);
assert.deepEqual(quicksort([2, 1]), [1, 2]);
assert.deepEqual(quicksort([1, 2, 6, 5]), [1, 2, 5, 6]);
assert.deepEqual(quicksort([1, 3, 3, 8, 10, 2, 6, 5]), [
  1,
  2,
  3,
  3,
  5,
  6,
  8,
  10,
]);

/**
 * Shell sort, O(n2) (worst known gap sequence), O(n log2n) (best known gap sequence)
 */
function shellSort(data) {
  var len = data.length;
  for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (var i = gap; i < len; i++) {
      var temp = data[i];
      var j = i;
      while (j >= gap && data[j - gap] > temp) {
        data[j] = data[j - gap];
        j -= gap;
      }
      data[j] = temp;
    }
  }
  return data;
}

// test
assert.deepEqual(shellSort([]), []);
assert.deepEqual(shellSort([2, 1]), [1, 2]);
assert.deepEqual(shellSort([1, 2, 6, 5]), [1, 2, 5, 6]);
assert.deepEqual(shellSort([1, 3, 3, 8, 10, 2, 6, 5]), [
  1,
  2,
  3,
  3,
  5,
  6,
  8,
  10,
]);

/**
 * Counting
 */

function countingSort(data, k = 11) {
  var count = [];
  var output = [];
  
  for (var i = 0; i < k; i++) {
    count.push(0)
  }

  for (var i = 0; i < data.length; i++) {
    const key = data[i];
    count[key] += 1;
  }

  var total = 0;
  for (var i = 0; i < k; i++) {
    const c = count[i];
    count[i] = total;
    total += c;
  }

  for (var i = 0; i < data.length; i++) {
    const key = data[i];
    output[count[key]] = key;
    count[key] += 1;
  }

  return output;
}

// test
assert.deepEqual(countingSort([]), []);
assert.deepEqual(countingSort([2, 1]), [1, 2]);
assert.deepEqual(countingSort([1, 2, 6, 5]), [1, 2, 5, 6]);
assert.deepEqual(countingSort([1, 3, 3, 8, 10, 2, 6, 5]), [
  1,
  2,
  3,
  3,
  5,
  6,
  8,
  10,
]);

/**
 * Swaps two elements of an array in-place by their indexes
 */
function swap(items, left, right) {
  var tmp = items[left];
  items[left] = items[right];
  items[right] = tmp;
  return items;
}

// test
assert.deepEqual(swap([1, 2], 0, 1), [2, 1]);