2
\$\begingroup\$

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?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.