TechBask

Learn | Explore | Share | Challenge Yourself | Enjoy | Make This World Beautiful Place To Live For Everyone|

Archive for the category “Computer Science”

Insertion sort in Javascript

These days, i am on spree to dive deep into javascript. As this is the exciting time for Javascript and it is finally getting accepted as full-fledged language, i thought to explore it at low level. How its basic predefined functions work. So i thought why not implement basic data structures and algorithms in javascript.

I’ll start with Sorting algorithms and first in the series is Insertion sort. Read more about insertion sort here.

Fun fact: The javascript V8 engine, virtual machine for Chrome browser uses Insertion sort for sorting objects with less than 23 elements and for more than that it uses Quick sort.

Note: Insertion sort performs well for sorting array with small number of elements.
Complexity: O(n*n) — worst case



function insertionSort(arrayOfNumbers){
	
	for(var i = 1; i < arrayOfNumbers.length; i++){

		var temp = arrayOfNumbers[i];

		var j = i-1;

		while(arrayOfNumbers[j] > temp && j >= 0){

			arrayOfNumbers[j+1] = arrayOfNumbers[j];
			j--;
		}

		arrayOfNumbers[j+1] = temp;
	}	
}


Post Navigation