k-arrays

gistfile1.js

'use strict';

//---------------------------------Array of k arrays ----------------------------------------

var kArrays = [];

var calcRandN = function () {
	return Math.floor(Math.random() * 100); //returns random number less than 100
}

var createArray = function () { //create random number of k-arrays with 5 random numbers
	var calcK = Math.floor(Math.random() * 30); //gives us a random # for arrays <30

	for (var i = 0; i < calcK; ++i) {
		kArrays.push([calcRandN(), calcRandN(), calcRandN(), calcRandN(), calcRandN()]);
		kArrays[i].sort(function(a,b){return a - b}) //sorts the 5 random #'s'
	}
	
	console.log(kArrays);
	return kArrays;
}

//-------------------------------------Brute Force method----------------------------------

var bruteForce = function () {
	var newArr = [];

	for (var i = 0; i < kArrays.length; i++) { //complexity of nested loop = O(n^2)
		for (var j = 0; j < kArrays[i].length; j++) {
			newArr.push(kArrays[i][j]);
		}
	}

	var fArr = newArr.sort(function(a, b){ //quicksort complexity = O(nlogn)
		return a - b;
	});	
	console.log('!!!!!!!!!!'); //for debugging
	console.log(fArr); //sorted output
}

/* final asymptotic complexity of Brute force = O(nLogn) + O(n^2) == O(n ^2) 
Tis SLOW!
*/

//--------------------------------------Quicksort using ECMAscript--------------------------

var quicksort = function () {
	/* Can also use the following reduce fxn to flatten which is O(n) in ECMA5

	kArrays.reduce(function(a, b) {
	    return a.concat(b);
	});

	*/

	var flatArray = kArrays.toString().split(',').map(function(x) { return parseInt(x); }); //one pass using map function --> O(n)
	//console.log(flatArray);

	var fArr = flatArray.sort(function(a, b){ //quicksort complexity = O(nlogn)
		return a - b;
	});	
	console.log('!!!!!!!!!!'); //for debugging
	console.log(fArr); //sorted output
}

/* asymptotic complexity of Quicksort = O(nLogn) + O(n) == O(nlogn)
   Space complexity of of quicksort is also O(log(n))
   Getting faster!
*/

//--------------------------------------Min Binry Heap----------------------------------------

var minHeap = function (scoreFunction) {

	this.content = [];
	this.scoreFunction = scoreFunction;

}

var flattenArr = function () {
	var flatArray = kArrays.toString().split(',').map(function(x) { return parseInt(x); }); //one pass using map function --> O(n)
	//console.log(flatArray);

	var fArr = flatArray.sort(function(a, b){ //quicksort complexity = O(nlogn)
		return a - b;
	});	

	return fArr;
}

minHeap.prototype = {
  push: function(element) {
    // Add the new element to the end of the array.
    this.content.push(element);
    // Allow it to bubble up.
    this.bubbleUp(this.content.length - 1);
  },

  pop: function() {
    // Store the first element so we can return it later.
    var result = this.content[0];
    // Get the element at the end of the array.
    var end = this.content.pop();
    // If there are any elements left, put the end element at the
    // start, and let it sink down.
    if (this.content.length > 0) {
      this.content[0] = end;
      this.sinkDown(0);
    }
    return result;
  },

  size: function() {
    return this.content.length;
  },

  bubbleUp: function(n) {
    // Fetch the element that has to be moved.
    var element = this.content[n], score = this.scoreFunction(element);
    // When at 0, an element can not go up any further.
    while (n > 0) {
      // Compute the parent element's index, and fetch it.
      var parentN = Math.floor((n + 1) / 2) - 1,
      parent = this.content[parentN];
      // If the parent has a lesser score, things are in order and we
      // are done.
      if (score >= this.scoreFunction(parent))
        break;

      // Otherwise, swap the parent with the current element and
      // continue.
      this.content[parentN] = element;
      this.content[n] = parent;
      n = parentN;
    }
  },

  sinkDown: function(n) {
    // Look up the target element and its score.
    var length = this.content.length,
    element = this.content[n],
    elemScore = this.scoreFunction(element);

    while(true) {
      // Compute the indices of the child elements.
      var child2N = (n + 1) * 2, child1N = child2N - 1;
      // This is used to store the new position of the element,
      // if any.
      var swap = null;
      // If the first child exists (is inside the array)...
      if (child1N < length) {
        // Look it up and compute its score.
        var child1 = this.content[child1N],
        child1Score = this.scoreFunction(child1);
        // If the score is less than our element's, we need to swap.
        if (child1Score < elemScore)
          swap = child1N;
      }
      // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.content[child2N],
        child2Score = this.scoreFunction(child2);
        if (child2Score < (swap == null ? elemScore : child1Score))
          swap = child2N;
      }

      // No need to swap further, we are done.
      if (swap == null) break;

      // Otherwise, swap and continue.
      this.content[n] = this.content[swap];
      this.content[swap] = element;
      n = swap;
    }
  },

  sortedArr: function() {
  	var sArr = [];

  	while (heap.size() > 0) {
  	  sArr.push((heap.pop()));
  	}

  	return sArr;
  }
};


/* asymptotic complexity of Minimum Heap = O(nLogn) + O(n) == O(nlogn)
   Space complexity of of minHeap is O(1)
   Worst case for minHeap is O(nlogn) which is better than the worst case for Quicksort.
   Space comlexity for minHeap is also better than Quicksort
*/

//------------------------------------------------------------------------------------------

/*TESTS*/

//Remove comments on each to run algorithms

createArray();
//bruteForce();
//quicksort();
// var heap = new minHeap(function(x){return x;});
// flattenArr().forEach(function(x){
// 	heap.push(x);
// });

// console.log(heap.sortedArr());