Вставка Сортировка справки в javascript - Khan Academy

Question

Я думаю, что я нахожусь на грани решения этого вопроса, но я не уверен, почему мой код не выполняется правильно. Может ли кто-нибудь дать мне некоторые отзывы и показать мне, где я испортился?

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, array.length -1, i); 
    } 
}; 

var array = [22, 11, 99, 88, 9, 7, 42]; 
insertionSort(array); 
println("Array after sorting: " + array); 
//Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]); 

, если я делаю это insert(array, array[i], i);, я получаю следующий результат:

Array after sorting: 22,11,12,100,89,10,8,43,5,,4,,1,,

Answer 1

Я думаю, у вас есть problème здесь:

в insert(array, array.length -1, i); должно быть insert(array, array.length -1, array[i]);

вы вставляли индекс массива instea d значения

также у вас есть массив из связанного в array[j + 1] = array[j];, потому что J старт с array.length -1, он должен быть array[j] = array[j-1]; в то время как j>0

последняя вещь: ваше rightIndex должно быть, я на каждой итерации не array.length -1.

Полный код:

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

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

     }; 

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

Answer 2

I got here another solution for this 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 = 0; i < array.length-1; i++){ 
     insert(array, i, array[i+1]); 
    } 
}; 

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

Answer 3

В вставки рода, мы разделим начальную несортированный массив на две части; сортированная часть и несортированная часть. Первоначально отсортированная часть имеет только один элемент (массив из 1 элемента - отсортированный массив). Затем мы выбираем элемент один за другим из несортированной части; вставить в отсортированную часть в правильное положение и развернуть отсортированную часть по одному элементу за раз.

var a = [34, 203, 3, 746, 200, 984, 198, 764, 9]; 

function insertionSort(values) { 
    var length = values.length; 
    for(var i = 1; i < length; ++i) { 
    var temp = values[i]; 
    var j = i - 1; 
    for(; j >= 0 && values[j] > temp; --j) { 
     values[j+1] = values[j]; 
    } 
    values[j+1] = temp; 
    } 
}; 

console.log(a); 
insertionSort(a); 
console.log(a); 

Answer 4

Я знаю, что я слишком поздно на вечеринке. Как вы знаете, есть несколько способов сделать это, но желтое существо на KA, по-видимому, хочет, чтобы мы сделали это определенным образом. Вот решение, которое сделало его счастливым:

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