Sort algorithms written in JS

bigO.js

var R = require("ramda");


function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function generateNumberList(size) {
  return R.map(i => getRandomInt(0, size), R.range(0, size));
}


var list = generateNumberList(1000);
var quickSortCount = 0;
var insertionSortCount = 0;
var mergeSortCount = 0;


function quickSort(list) {
  quickSortCount++;
  var len = R.length(list);
  if (len == 0 || len == 1) return list;
  var pivot = R.last(list);

  var firstHalf = R.filter(i => i<= pivot, R.init(list));
  var secondHalf = R.filter(i => i> pivot, R.init(list));
  return R.concat(quickSort(firstHalf), R.prepend(pivot, quickSort(secondHalf)));
}


function insert(val, result) {
  insertionSortCount++;
  var head = R.head(result);
  var len = R.length(result);
  if (len > 0 && val > head) {
    result = R.insert(0, head, insert(val,  R.tail(result)));
  } else {
    result = R.insert(0, val, result);
  }
  return result;
};

function insertionSort(input) {
  insertionSortCount++;
  var len = R.length(input);
  if (len == 0 || len == 1) return input;
  return insert(R.head(input), insertionSort(R.tail(input)));
}


function merge(a, b) {
  mergeSortCount++;
  if (R.length(a) == 0) return b;
  if (R.length(b) == 0) return a;

  var headA = R.head(a);
  var headB = R.head(b);
  var tailA = R.tail(a);
  var tailB = R.tail(b);

  return headA <= headB ?
    R.insert(0, headA, merge(tailA, b)) :
    R.insert(0, headB, merge(a, tailB));
}

function mergeSort(list) {
  mergeSortCount++;
  var len = R.length(list);
  if (len == 0 || len == 1) return list;
  var firstHalf = R.slice(0, len/2, list);
  var secondHalf = R.slice(len/2, len, list);
  return merge(mergeSort(firstHalf), mergeSort(secondHalf));
}


quickSort(list);
//insertionSort(list);
//mergeSort(list);
console.log("Array lenght: " + R.length(list));
console.log("Function calls:");
console.log("INSERTION SORT:", insertionSortCount);
console.log("MERGE SORT:", mergeSortCount);
console.log("QUICK SORT:", quickSortCount);

bigO.txt

http://bigocheatsheet.com/

Avarage
INSERTION SORT: O(n^2)
MERGE SORT: O(n log(n))
QUICK SORT: O(n log(n))



Array lenght: 1000000
Function calls:
INSERTION SORT: RangeError: Maximum call stack size exceeded
MERGE SORT: RangeError: Maximum call stack size exceeded
QUICK SORT: 1354895


Array lenght: 1000
Function calls:
INSERTION SORT: 249612
MERGE SORT: 11726
QUICK SORT: 1353

insertionSort.js

var R = require("ramda");


function insert(val, result) {
  var head = R.head(result);
  var len = R.length(result);
  if (len > 0 && val > head) {
    result = R.insert(0, head, insert(val,  R.tail(result)));
  } else {
    result = R.insert(0, val, result);
  }
  return result;
};

function insertionSort(input) {
  var len = R.length(input);
  if (len == 0 || len == 1) return input;
  return insert(R.head(input), insertionSort(R.tail(input)));
}

console.log('INSERTION SORT:', insertionSort([1, 9, 3, 10, 5, 4, 6, 7, 8, 2]));

mergeSort.js

var R = require("ramda");


function merge(a, b) {
  if (R.length(a) == 0) return b;
  if (R.length(b) == 0) return a;

  var headA = R.head(a);
  var headB = R.head(b);
  var tailA = R.tail(a);
  var tailB = R.tail(b);

  return headA <= headB ?
    R.insert(0, headA, merge(tailA, b)) :
    R.insert(0, headB, merge(a, tailB));
}

function mergeSort(list) {
  var len = R.length(list);
  if (len == 0 || len == 1) return list;
  var firstHalf = R.slice(0, len/2, list);
  var secondHalf = R.slice(len/2, len, list);
  return merge(mergeSort(firstHalf), mergeSort(secondHalf));
}

console.log('MERGE SORT:', mergeSort([1, 9, 3, 10, 5, 4, 6, 7, 8, 2]));

quickSort.js

var R = require("ramda");

function quickSort(list) {
  var len = R.length(list);
  if (len == 0 || len == 1) return list;
  var pivot = R.last(list);

  var firstHalf = R.filter(i => i<= pivot, R.init(list));
  var secondHalf = R.filter(i => i> pivot, R.init(list));
  return R.concat(quickSort(firstHalf), R.prepend(pivot, quickSort(secondHalf)));
}

console.log('QUICK SORT:', quickSort([1, 9, 3, 10, 5, 4, 6, 7, 8, 2]));