Почему существует разница между использованием переменной и вызовом индекса непосредственно внутри цикла?

Question

Я изучаю сортировку вставками, и я заметил, что мой код работает, только когда я использую переменную (num) для сравнения со значением myArray[j].

Меня смущает вопрос, почему myarray [i] не работает, поскольку для num установлено значение myarray [i] и поскольку myarray [j] вложено в цикл, значение i не изменяется. Так почему же метод работает правильно, только если я использую (num) для сравнения?

const myArray = [3,1,4,8,2,7,3,23,43,21,46,23,30,49,50,12,44,233,492,32];

const insertionSort = (myArray) => {
    for (let i = 1;i<myArray.length;i++){
        let num = myArray[i];
        j = i-1
        while (j>=0 && myArray[j]>num){
            myArray[j+1] = myArray[j]
            j--
        }
        myArray[j+1] = num
    }
}

// correctly outputs [ 1, 2, 3, 3, 4, 7, 8, 12, 21, 23, 23, 30, 32, 43, 44, 46, 49, 50, 233, 492 ]



const insertionSort = (myArray) => {
    for (let i = 1;i<myArray.length;i++){
        let num = myArray[i];
        j = i-1
        while (j>=0 && myArray[j]>myArray[i]){
            myArray[j+1] = myArray[j]
            j--
        }
        myArray[j+1] = num
    }
}

// incorrectly outputs [ 1, 3, 4, 2, 7, 3, 8, 23, 21, 43, 23, 30, 46, 49, 12, 44, 50, 233, 32, 492 ]

Answer 1

Учитывая этот простой массив и давайте предположим, что мы используем нерабочий алгоритм:

 //    i
   [2, 3, 1]
 // j

Вы бы начали сортировку вставок с i = 1 и num = 3. array[i] также 3 в начале. Теперь, когда array[j] (2) меньше 3, мы продолжим сортировку по следующему индексу.

 //       i
   [2, 3, 1]
 //    j

Теперь i = 2, num - это 1 и array[i] - тоже 1 (пока). Поскольку array[i] (1) меньше array[j] (3), происходит смещение вправо:

 //       i
 //     >>>
   [2, 3, 3]
 //    j

Цикл теперь должен продолжаться до j = 0, так как 1 должен быть вставлен до 2 и 3, и если бы мы могли сравнить num (1) с array[j] (2), внутренний цикл продолжился бы, но по мере того, как вы возьмите array[i] (3), цикл останавливается:

  //       i
    [2, 3, 3]
 //  j

, чем вставка происходит в неправильном положении:

 //    v
   [2, 1, 3]

Answer 2

взгляните на прототипы массивов ES6, например .map()

Я изменил ваш код для использования .map(), и проблема, с которой вы столкнулись при использовании myArray[i] в цикле while, исчезла + код, на мой взгляд, выглядит чище.

const insertionSortEs6 = (array) => {
    array.map((el, index) => {
    j = index - 1

    while (j>=0 && array[j] > array[index]){
      array[j+1] = array[j]
      j--
    }
    array[j+1] = array[index]
  })
  return array
}

По какой-то причине ваш myArray[i] мутирует во время цикла. Я попытался выделить проблему с консольными журналами: https://jsfiddle.net/4mv5x8cb/47/. Я полагаю, что это пролит некоторый свет на проблему, см. URL:

Тем не менее, я не на 100% уверен, почему происходит эта мутация, поэтому я хотел бы услышать, если кому-то еще нечего добавить по этому вопросу.

Вот экран вывода консоли:

Answer 3

В while (j>=0 && myArray[j]>myArray[i]) во время итераций значение myArray[i] изменяется, но num не изменяется.