Insertion Sort what i code, doesn't get result correctly

Noumi 0
Viewed 40
let Array = [31, 41, 59, 26, 41, 58]
let len = Array.length;

for (let j=1; j < len; j++) {
    let key = Array[j]
    console.log(key)
    let i = j-1
    while(i > 0 && Array[i] > key) {
        Array[i+1] = Array[i]
        i = i-1
    }
    Array[i+1] = key
}

console.log(Array)

Output: [ 31, 26, 41, 41, 58, 59 ]

Why the result doesn't correct? I didn't know what the problem here. Can anyone help me?

insertion-sort javascript
1 Answers

You should not name your variables using names of the built-in objects that ship with JavaScript.

[1] Your variable Array is in fact overriding the Array object of JavaScript. To fix that, you simply name your variables with something that doesn't override built-in objects.

Also, the while loop that iterates over the sub array should account for the index 0 so that loop declaration should be while (i >= 0 && arr[i] > key).

Here's a working demo with some useful explanations:

/** "Array" is renamed into "arr" in order to prevent overriding built-in Array object */
let arr = [31, 41, 59, 26, 41, 58],
  len = arr.length;

/** loop through the entire array */
for (let j = 1; j < len; j++) {
  /** cache the current elemnt in a variable so it can be used along the way */
  const current = arr[j];
  /** the max index of the sub array */
  let i = j - 1;
  /**
   * loop over the sub array, account for index "0" as well so we get proper permutations.
   * Also decrement "i" by a value of "1".
   */
  while (i >= 0 && arr[i] > current) arr[i + 1] = arr[i--];
  arr[i + 1] = current;
}

/** print the result */
console.log(arr)

[1] : For everyone, that second phrase of my answer may not be very correct in the case of the OP's code.
In fact the built-in Array object will not get overridden. That seems misleading but I have said so in purpose to recommend NOT naming variables with built-in objects names.
Anyway, if the let keywords here let Array = [...] was accidently omitted then that's another story which will eventually override the Array built-in object which is really not recommended.
I have just tested that even using let the built-in Array object gets overridden!

ths0
Related