November 11, 2014 · javascript algorithms

Insertion Sort JavaScript

I will start mini blog post series about Algorithms and their implementation in JavaScript. This is first post in series so Insertion Sort algorithm represents adequate choice. Insertion sort is quite simple algorithm. It has a time complexity of Θ(n2), thus being slower than heapsort or for example merge sort.

Script can be run in Windows enviorment by invoking folowing command from cmd promt:

 CScript file_name.js

Implementation details (insertionSort.js)

 // Stankovic Vlada (svlada@gmail.com)
 // Insertion Sort

 var debug=1;

 // Basic list
 var list = [4, 1, 8, 7, 2, -2, 2, 2, 2, 3, 4, 5, 3];
 insertionSort(list);

 if (debug == 1) 
     WScript.echo(list);

 // Multiple lists
 var map = {
     "lists" : [
         {"arr": [6, 5, 4, 3, 2, 1]},
         {"niz": [8, 3, 4, 7, 2, 1]},
         {"niz1": [2, 1, 1, 1]}
     ]
 };

 for(var i = 0; i < map.lists.length; i++) {
     for(var key in map.lists[i]) {
         if(map.lists[i].hasOwnProperty(key)) {
             insertionSort(map.lists[i][key])
             if (debug==1) 
                 WScript.echo(map.lists[i][key]);
         }
     }
 }

 // Insertion Sort function
 function insertionSort(list) {
     for (var j = 1; j < list.length; j++) {
         var key = list[j];
         var i = j - 1;
         while (i >= 0 && key < list[i])     {
             list[i+1] = list[i];
             i = i - 1;
         }
         list[i+1] = key;
     }
 }
  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket
Comments powered by Disqus