Ханская академия: цикл JavaScript занимает слишком много времени

Question

Я читаю курс ханской академии по алгоритмам. Я нахожусь на https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/p/challenge-implement-insertion-sort. Пока что у меня есть:

var insert = function(array, rightIndex, value) {
for(var j = rightIndex;
    j >= 0 && array[j] > value;
    j--) {
    array[j + 1] = array[j];
}   
array[j + 1] = value; 
};

var insertionSort = function(array) {

for(var i= 1;  i < array.length ; i++ ) {
    insert(array, i ,array[i+1] );
}

};

var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);

Вы можете увидеть строку кода на скриншоте, которая кажется проблемой, но она выглядит хорошо для меня. Что я делаю неправильно?

Answer 1

Вы начинаете rightIndex в i и перемещение значения array[i + 1], но i достигает array.length а также insert начинается с установки элемента в rightIndex + 1, Это приведет к росту массива.

Переместите текущий элемент и начните с предыдущего индекса:

for (var i = 1; i < array.length; i++) {
    insert(array, i - 1,array[i]);
}

Один из способов поймать это при отладке - запечатать ваш массив, чтобы он не мог расти:

var array = Object.seal([22, 11, 99, 88, 9, 7, 42]);

Это работает только в строгом режиме. Если вы находитесь в небрежном режиме, он просто будет скрывать ошибки.