Friday 25 October 2013

My own implementation of MergeSort

Took me an hour to nut out ... but I did it by myself without looking at the wikipedia's implementation!

Probably not the best way to implement it ... but I don't care at the moment, just feel happy that I did it :-)

 <html>  

      <script>
           function merge(left, right){
                var result = new Array();
                while (left.length > 0 || right.length > 0){
                     var smallestElement;
                     if (left.length > 0 && right.length > 0){
                          smallestElement = left[0];
                          if (left[0] > right[0]){
                               smallestElement = right[0];
                               right.splice(0,1);
                          } else {
                               left.splice(0, 1);
                          }
                     } else if (left.length > 0){
                          smallestElement = left[0];
                          left.splice(0, 1);
                     } else {
                          smallestElement = right[0];
                          right.splice(0,1);
                     }
                     result.push(smallestElement);
                }
                return result;
           }
           function mergeSort(input){
                var length = input.length;
                var left = input.splice(0, length/2);
                var right = input;
                var leftResult;
                var rightResult;
                if (left.length > 1){
                     leftResult = mergeSort(left);
                } else {
                     leftResult = left;
                }
                if (right.length > 1){
                     rightResult = mergeSort(right);
                } else {
                     rightResult = right;
                }
                return merge(leftResult,rightResult);          
           }
           (function(){
                var testInput = new Array(6,5,3,4,2,1,8,8,9,9,10,15);
                console.log(mergeSort(testInput));
           }());
      </script>
 </html>

Posted by at 1 comment:

Monday 7 October 2013

__proto__ vs .prototype

What is __proto__?

Every object in javascript has a __proto__ property.

The __proto__ property points to object that this object inherits from.

By default an object non-function points to Object.prototype.
(Object.prototype is basically the root object, and its __proto__ is null) i.e. (Object.prototype.__proto__) is null.

By default an function object points to Function.prototype (Function.prototype this is where function inherits methods like .apply(), .call(), etc...)
Function.prototype__proto__ points to Object.prototype.

Invoking a function as a constructor
This basically just means calling a function using the keyword new.

 When you do that the __proto__ of  object created becomes the functions ".prototype" which by default which will be Object.prototype.

NOTE this is not the same as the function object's __proto__ which is Function.prototype.

I.e. by default:
var y = function(){}

y.__proto__ = Function.prototype
y.prototype = Object.prototype

What is .prototype?
By setting .prototype on a function object which is going to be invoked as a constructor, we are basically setting the __proto__ property for the object that is goingto be created using this function.

To Summarize

 var x = {};
// x.__proto__ = Object.prototype

var f = function(){};
// f.__proto__ = Function.prototype
// f.prototype = Object.prototype

f.prototype = x;
// f.__proto__ = Function.prototype
// f.prototype = x (duh!)

var y = new f();
// y.__proto__ = x;

Posted by at No comments:
Labels: , , ,
Subscribe to: Posts (Atom)