Implementation of insertion sort in JavaScript

Question

I have written an insertion sort algorithm in JavaScript:

function insertionSort(inputArray){ 
 var totalElements = inputArray.length - 1;
 var temp = 0;
 var lastIndex = 0;
 var prevIndex = 0;
 for(var i = 0; i <= totalElements; i++){
 for(var currentIndex = i; currentIndex > lastIndex; currentIndex--){
 prevIndex = currentIndex - 1; 
 if(inputArray[currentIndex] < inputArray[prevIndex]){
 temp = inputArray[currentIndex];
 inputArray[currentIndex] = inputArray[prevIndex];
 inputArray[prevIndex] = temp; 
 }else{
 break;
 }
 }
 }
 return inputArray;
}
console.log(insertionSort([1,31,26,4,3,12]));
console.log(insertionSort([5,6,1,2,3,4])); 

The output is also proper:

rahul@rahul:~/myPractise/Algo$ node sorting.js 
[ 1, 3, 4, 12, 26, 31 ]
[ 1, 2, 3, 4, 5, 6 ]
rahul@rahul:~/myPractise/Algo$

Can this be further improved?

Answer 1

Your function can only sort numbers and strings

The built in Array.sort function offers an optional compare function as a parameter. Adding this feature to your insertionSort function would allow for users to sort any type of object:

function defaultCompare(x, y) {
 if (x < y)
 return -1;
 else if (x > y)
 return 1;
 else
 return 0;
}
function insertionSort(array, compare) {
 compare = compare ? compare : defaultCompare;
 //...
}

You have quite a few variables that aren't necessary

totalElements

You only use this variable once, in the condition of your first for loop. JavaScript has some incredibly fast engines and with JIT-Compiler (just in time compiler) you don't have to worry about micromanaging optimizations like what if js isn't smart enough to know that it's recalculating inputArray.length - 1 each iteration. Defining totalElements arguably makes your code harder to read by adding another variable the scope, and the JS engines are smart-enough/fast-enough that performance isn't likely affected, so I would recommend getting rid of it.

temp

You could eliminate temp by abstracting out a function to swap indices in an array:

function swapIndices(array, index1, index2) {
 var temp = array[index1];
 array[index1] = array[index2];
 array[index2] = temp;
}

This also improves your code's cohesiveness by abstracting out the technicalities of swapping variables, and it allows you to use swapIndices elsewhere in your code.

lastIndex

This one is just a constant for zero. At the very least you should change the var to const:

const lastIndex = 0;

But I'd recommend to just get rid of it.

prevIndex

I find currentIndex - 1 more clear than prevIndex. The former is obviously the index 1 less than currentIndex whereas the latter could also mean the previously swapped element (precedingIndex is another possible name).

Summary

With all the above changes your code would look like:

function defaultCompare(x, y) {
 if (x < y)
 return -1;
 else if (x > y)
 return 1;
 else
 return 0;
}
function swapIndices(array, index1, index2) {
 var temp = array[index1];
 array[index1] = array[index2];
 array[index2] = temp;
}
function insertionSort(array, compare) {
 compare = compare ? compare : defaultCompare;
 for (let i = 0; i < array.length; i++) {
 for (let currIndex = i; currIndex > 0; currIndex--) {
 if (compare(array[currIndex], array[currIndex - 1]) < 0) {
 swapIndices(array, currIndex, currIndex - 1);
 }
 else {
 break;
 }
 }
 }
 return array;
}

Answer 2

After reading and running your code, I thought I could make your life easier by turning this pseudocode at Insertion Sort to javascript.

 function insertionSort(inputArray){
 var holePosition
 var valueToInsert
 
 for(var i = 1; i< inputArray.length; i++){
 
 /* select value to be inserted */
 valueToInsert = inputArray[i]
 holePosition = i
 
 /* Notice I used the while as opposed to the for*/
 while ( holePosition > 0 && inputArray[holePosition-1] > valueToInsert){
 inputArray[holePosition] = inputArray[holePosition-1]
 holePosition = holePosition -1
 
 }
 /* insert the number at hole position */
 inputArray[holePosition] = valueToInsert
 }
 return inputArray;
 }
var result =insertionSort([1,31,26,4,3,12]);
alert('['+ result.join() + ']');

Note:

• So many variables were defined totalElements, temp, lastIndex and prevIndex which were unnecessary. In the code below, I utilised two variables called holePosition and valueToInsert to serve as Positions for insertion and the values to include in those positions
• I have also replaced your second for statement with a while loop. I would use while loop with a continuous sorting as opposed to a for loop