1

I'm writing the Insertion Sort algorithm in JavaScript.

I have a small bug, however, as follows:

function insertionSort(arrayOfNumbers) {
  var j, key, i, length

  for (j = 1, length = arrayOfNumbers.length; j < length; j++) {
    key = arrayOfNumbers[j]
    i = j - 1
    while (i >= 0 && arrayOfNumbers[i] > key) {
      arrayOfNumbers[i + 1] = arrayOfNumbers[i];
      i = i - 1
    }
    arrayOfNumbers[i + 1] = key
  }

  return arrayOfNumbers
}

alert(insertionSort([2, 1, 5, 8, 9]))

I've written up the pseudo code version of the algorithm as follow:

for j <- 2 to n

  do key <- A[ j ]

    i <- j - 1

    while i > 0 and A[ i ] > key

      do A[ i + 1 ] <- A[ i ]

        i <- i - 1

      A[ i + 1 ] <- key

Can you spot my error?

Improve this question
0

2 Answers 2

Reset to default
2

do .. while is not equivalent to pseudo code WHILE .. DO ... You also need to adjust your algorithm to zero based indexing (you did so, but only partially).

See fix:

function insertionSort(arrayOfNumbers) {
  var j, key, i, length

  for (j = 1, length = arrayOfNumbers.length; j < length; j++) {
    key = arrayOfNumbers[j]
    i = j - 1
    while (i >= 0 && arrayOfNumbers[i] > key){
      arrayOfNumbers[i + 1] = arrayOfNumbers[i];
      i = i - 1
    } 
    arrayOfNumbers[i + 1] = key
  }

  return arrayOfNumbers
}

var result = insertionSort([2, 1, 5, 8, 9]);
console.log(result);

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

the problem is that you shift the 2 unconditionally to the end of the array.

key = arrayOfNumbers[j]
i = j - 1
do {
  arrayOfNumbers[i + 1] = arrayOfNumbers[i];
  i = i - 1
} while (i > 0 && arrayOfNumbers[i] > key)
arrayOfNumbers[i + 1] = key

You start with element 1 (which is 1) and i is set to 0. Then unconditionally you shift element 0 to element 1 and insert your key (old element 1) into element 0.

In the next iteration you unconditionally shift element 1 (which is now that 2) to element 2, and so on.

Improve this answer

Comments