JavaScript Selection Sort

The selection sort is a very primitive sort that has two loops. They are both imbricated which cause an asymptotic analysis of the upper bound to be O(n^2). The selection sort loops a first time all elements except the last one of the array which allow to evaluate every data. The second loop, is there to find the smallest value after the first loop and swap any smallest value if one found.

The idea is : find the smallest one, put it at the beginning.

function swap(array, left, right)
{
    var temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}
 
function selectionSort(arrayToSort){
  var length = arrayToSort.length;
  var minIndex = -1;
  for (var i = 0; i < length-1; i++)
  {
    minIndex = i;
    for (var j = i+1; j < length; j++){
      if (arrayToSort[j] < arrayToSort[minIndex]){
        minIndex = j;
      }
    }
    if(minIndex !== i){
        swap(arrayToSort, minIndex, i);
    }
  }
}

JavaScript Exponential Search

An exponential search is a search the binary search with a little difference that it will try to not have to divide in two the whole array but just a subset. This subset is decided by jumping in the array in an exponential way. At some point, the value found will be bigger than the one searched which is where we stop jumping and applying the binary search.

The first step is to bring the binary search:

function binarySearch(arrayToSearch, valueToSearch, start, end){
  if(start <= end){
    var middle = Math.ceil((end + start)/2)
    var middleValue = arrayToSearch[middle];
    if(middleValue === valueToSearch){
      return middle;
    } else if(valueToSearch < middleValue){
        end = middle - 1;
    } else{
        start = middle + 1;
    }
    return binarySearch(arrayToSearch, valueToSearch, start, end);
  }
  return -1;
}

The exponential search come right before:

function exponentialSearch(arrayToSearch, valueToSearch, length){
  
    if (arrayToSearch[0] == valueToSearch){
        return 0;
    }

    var i = 1;
    while (i < length && arrayToSearch[i] <= valueToSearch){
        i = i*2;
    }
 
    return binarySearch(arrayToSearch, valueToSearch, i/2, Math.min(i, length-1));
}

Even with this optimization, the search still at O(log n). As we can see on the last line, we call the binary search by not starting with zero, but with the value found with the exponential while.

JavaScript Interpolation Search

If an array contains element that are uniformly distributed, it’s possible to each an asymptotic analysis of Big O(log log n).

The whole problem is about determining the position. This is done by finding the position. This is the iterative solution.

var arrayToSearch = [2, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 31, 35];

console.log("Found at position :" + interpolationSearch(arrayToSearch, 2));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 12));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 35));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 44444));

function interpolationSearch(arrayToSearch, valueToSearch){
  var length = arrayToSearch.length;
  var low = 0;
  var high = length-1;
  var position = -1;
  var delta = -1;
  while(low <= high 
        && valueToSearch >= arrayToSearch[low]
        && valueToSearch <= arrayToSearch[high]){
    delta = (valueToSearch-arrayToSearch[low])/(arrayToSearch[high]-arrayToSearch[low]);
    position = low + Math.floor((high-low)*delta);
    if (arrayToSearch[position] == valueToSearch){
      return position;
    }
    if (arrayToSearch[position] < valueToSearch){
      low = position + 1;
    } else {
      high = position - 1;
    }
  }

  return -1;
}

This can be easily transformed into the a recursive algorithm.

var arrayToSearch = [2, 6, 8, 12, 14, 16, 20, 24, 26, 28, 30, 31, 35];
var length = arrayToSearch.length;
var low = 0;
var high = length-1;
console.log("Found at position :" + interpolationSearch(arrayToSearch, 2, 0, high));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 12, 0, high));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 35, 0, high));
console.log("Found at position :" + interpolationSearch(arrayToSearch, 44444, 0, high));

function interpolationSearch(arrayToSearch, valueToSearch, low, high){
  if(low <= high 
        && valueToSearch >= arrayToSearch[low]
        && valueToSearch <= arrayToSearch[high]){
    var delta = (valueToSearch-arrayToSearch[low])/(arrayToSearch[high]-arrayToSearch[low]);
    var position = low + Math.floor((high-low)*delta);
    if (arrayToSearch[position] == valueToSearch){
      return position;
    }
    if (arrayToSearch[position] < valueToSearch){
      low = position + 1;
    } else {
      high = position - 1;
    }
    return interpolationSearch(arrayToSearch, valueToSearch, low, high)
  }

  return -1;
}

JavaScript Jump Search

The Jump Search algorithm allows to combine a linear search with a speed optimization. This mean that instead of going 1 by 1, we will increase the step of √n and increase that step of √n which make the step getting bigger and bigger.

The asymptotic analysis of Jump Search is o(√n). Like the binary search, it needs to be sorted. The advantage against binary search is that Jump Search traversed back only once.

var arrayToSearch = [2, 6, 8, 12, 43, 78, 99, 134, 144, 156, 199, 256, 500];

console.log("Found at position :" + jumpSearch(arrayToSearch, 2));
console.log("Found at position :" + jumpSearch(arrayToSearch, 256));
console.log("Found at position :" + jumpSearch(arrayToSearch, 500));
console.log("Found at position :" + jumpSearch(arrayToSearch, 44444));

function jumpSearch(arrayToSearch, valueToSearch){
  var length = arrayToSearch.length;
  var step = Math.floor(Math.sqrt(length));
  var index = Math.min(step, length)-1;
  var lowerBound = 0;
  while (arrayToSearch[Math.min(step, length)-1] < valueToSearch)
  {
    lowerBound = step;
    step += step;
    if (lowerBound >= length){
      return -1;
    }
  }
  
  var upperBound = Math.min(step, length);
  while (arrayToSearch[lowerBound] < valueToSearch)
  {
    lowerBound++;
    if (lowerBound == upperBound){
      return -1;
    }
  }
  if (arrayToSearch[lowerBound] == valueToSearch){
     return lowerBound;
  }
  return -1;
}

It requires two loops. The first loop looks at value to determine if the value is under or not the jump. This one will set the lower bound variable that contains the lower bound of the linear search. The second loop does the linear from the lower bound to the upper bound. The upper bound can be the end of the array, or if a step.

JavaScript Binary Search

Previously we say the linear search which is having an asymptotic upper bound of O(n). This time, we increase the speed with a binary sort of O(log(n)). The speed is increased at the cost of having the requirement of initial array to be sorted.

var arrayToSearch = [2, 6, 8, 12, 43, 78, 99, 134, 144, 156, 199, 256, 500];

console.log("Found at position :" + binarySearch(arrayToSearch, 2));
console.log("Found at position :" + binarySearch(arrayToSearch, 256));
console.log("Found at position :" + binarySearch(arrayToSearch, 500));
console.log("Found at position :" + binarySearch(arrayToSearch, 44444));

function binarySearch(arrayToSearch, valueToSearch){
  var start = 0;
  var end = arrayToSearch.length - 1;

  while(start <= end){
    var middle = Math.ceil((end + start)/2)
    var middleValue = arrayToSearch[middle];
    if(middleValue === valueToSearch){
      return middle;
    } else if(valueToSearch < middleValue){
        end = middle - 1;
    } else{
        start = middle + 1;
    }
  }
  return -1;
}

The idea is so split the array in 2, then look in which half the value may be. If the value is lower than the middle value, we divide reject the upper half. We keep doing it until we found the value or that the gap between the lower and upper bound doesn’t exist.

In the case of finding 256, the lower bound start with the first index (value 2) and the length-1 (value 500). The middle is index 6 (value 99). Since we are searching for 256 the value above 99, hence we reject all values on the left (index 0 to index 6 inclusively). To do so, we move the start to index 6+1 (value 134) and keep the end bound to length-1 (500). And we iterate.

The first algorithm is using a while to loop through, but as we just described, we are doing over and over the same thing, just with a reduction of the array. It means that it’s like asking for different array the same logic. This means that we can transform the iterative approach into a recursive approach.

var arrayToSearch = [2, 6, 8, 12, 43, 78, 99, 134, 144, 156, 199, 256, 500];
var start = 0;
var end = arrayToSearch.length - 1;

console.log("Found at position :" + binarySearch(arrayToSearch, 2, start, end));
console.log("Found at position :" + binarySearch(arrayToSearch, 256, start, end));
console.log("Found at position :" + binarySearch(arrayToSearch, 500, start, end));
console.log("Found at position :" + binarySearch(arrayToSearch, 44444, start, end));

function binarySearch(arrayToSearch, valueToSearch, start, end){
  if(start <= end){
    var middle = Math.ceil((end + start)/2)
    var middleValue = arrayToSearch[middle];
    if(middleValue === valueToSearch){
      return middle;
    } else if(valueToSearch < middleValue){
        end = middle - 1;
    } else{
        start = middle + 1;
    }
    return binarySearch(arrayToSearch, valueToSearch, start, end);
  }
  return -1;
}

JavaScript Linear Search

Linear search is a basic search that is slow. Slow in the magnitude of having an asymptotic analysis of a BigO of O(n). This is the worse case is that the item is at the last position which require to traverse the whole array. Linear search moves one to one and check the value. It has the advantage of not needing to have an input sorted.

var arrayToSearch = [7,23,4,23,87,2,6,3,213,43,34,1,76,43];

console.log("Found at position :" + linearSearch(arrayToSearch, 34));

function linearSearch(arrayToSearch, valueToSearch){
  var length = arrayToSearch.length;
  for(var i = 0; i < length ; i++){
    if(arrayToSearch[i] === valueToSearch){
      return i;
    }
  }
  return -1;
}

Here is a naive implementation where -1 is returned in the case of no element found. As you can see, the function is under the invocation of the function. This is possible because of JavaScript’s hoisting mechanism that move function declaration at the beginning of the scope (not function expression).

A recursive solution is also possible :

console.log("Found at position :" + linearSearch(arrayToSearch, 34, 0));
 
function linearSearch(arrayToSearch, valueToSearch, index){
  if(arrayToSearch.length === 0){
    return -1;
  }
  if(arrayToSearch[0] === valueToSearch){
    return index;
  }
  return linearSearch(arrayToSearch.slice(1), valueToSearch, index + 1);
}

The idea is to recursively remove the first element of the array and pass it down to the method again and again until the array is empty or the value is found.

JavaScript Part 6 : Create Instance without new or object.create (Functional Approach)

We saw in a previous article how to create a new object with “new”, and also without “new”. Both of them were using the prototype chain for inheritance. Here is a way to avoid using the prototype chain and be able to use object literal with function only to create instance.

Let’s start without any inheritance with a first object that we will create from “myFactory” function. This one take parameters like a normal constructor. It could be a single string like in this example, or a more complex object. What is important is that factory create a new literal object which is private until we return this one. Within this factory, every “var” will be private, hence having a good advantage against the classical approach where every variable attache to “this” are public. On this functional approach, we hook all public method to the returned value, in that case the container.

var myFactory = function (p1){
  var privateContainer = {};
  var private = "Private";
  
  privateContainer.publicMethod = function(){console.log("Can access private variable like : " + private1 + " or the param " + p1)};
  
  return privateContainer;
}

var instance1 = myFactory("i1");
var instance2 = myFactory("i2");

instance1.publicMethod();
instance2.publicMethod();

If we want to inherit, we need to assign members to the object literal by using the base class factory. There is many ways to do it. The way presented is that every public members of the base class will be exposed through the child class. This is done by adding the children members to the base instance instead of adding the, to an empty object. However, we could have kept the empty literal object and create public method that proxied the base class if we wanted to manually decide which public property of the base class to expose.

var myBaseFactory = function (p2){
  var privateContainer = {};
  var private = "PrivateBase";
  
  privateContainer.publicMethodInBase = function(){console.log("[BASE] Can access private variable like : " + private + " or the param " + p2)};
  
  return privateContainer;
}

var myFactory = function (p1){
  var privateContainer = myBaseFactory("Base!" + p1);
  var private = "Private";
  privateContainer.publicMethod = function(){console.log("Can access private variable like : " + private + " or the param " + p1)};
  
  return privateContainer;
}

var instance1 = myFactory("i1");
var instance2 = myFactory("i2");

instance1.publicMethod();
instance1.publicMethodInBase();
instance2.publicMethod();
instance2.publicMethodInBase();

Here is the output:

"Can access private variable like : Private or the param i1"
"[BASE] Can access private variable like : PrivateBase or the param Base!i1"
"Can access private variable like : Private or the param i2"
"[BASE] Can access private variable like : PrivateBase or the param Base!i2"

This way offer a clean and simple way to create instances without the complexity of the prototype chain. It has the disadvantage of not sharing with the prototype, hence will be more heavy in term of memory. It has the advantage to encapsulate functions and variables inside the factory and to not expose them.

JavaScript Prototype Part 5 : Inheritance without “new” (Prototypal Approach)

There is so many different ways to do something in JavaScript that become overwhelming to know which one to use. In this article, we will a different way to create multiple instances of an object with a base class without using the keyword “new”. If you want to see, how to use “new”, you can see that past article about how to create inheritance with JavaScript.

Let’s create a simple literal object that define a member and a function.

let baseClass1 = {
  memberbase: "base",
 
  functionbase () {
    return "This is memberbase value ("+this.memberbase+") with access to the child value ("+this.memberchild+")";
  }
};

The child class, that will inherit the base class, needs to be dynamically called and return a new instance every time invoked. To do so, without using “new”, we need to use two Object methods. The first one is Object.assign which extends the base class with the child literal object. The second one is Object.create which create the hierarchy with the prototype.

let childClass1 = function childFactory () {
  return Object.assign(Object.create(baseClass1), {
    memberchild:"child"
  });
};

To consume this creation pattern, we only need to call the childClass1 function.

let instance1 = childClass1();
let instance2 = childClass1();
instance2.memberchild="child 2";

console.log(instance1.memberchild);     // child
console.log(instance2.memberchild);     // child 2
console.log(instance1.functionbase());  // This is memberbase value (base) with access to the child value (child)
console.log(instance2.functionbase());  // This is memberbase value (base) with access to the child value (child 2)

This works, like working with the new pattern. The difference is that we are not calling the base class from the child constructor, but instead having a factory that use assign and create. While we were using Object.create to assign the prototype of the child to match up the base one with the “new” pattern, in that case we touch the prototype because Object.create first parameter is to assign the prototype.

The reason is that we are using assign to merge the two literal objects into a single one — there is not need to play with “real” hierarchy. Finally, we do not need to set the constructor of the child class, because we do not instantiate with the keyword new.