TechBask

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

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;
	}	
}


Advertisements

Single Post Navigation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: