Insertion Sort help in javascript -- Khan Academy

Question

I think I am on the verge of solving this but Im not sure why my code is not executing correctly. Can someone provide some feedback for me and show me where I messed up?

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]);

if I do this insert(array, array[i], i);,I get the following output:

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

Answer 1

I think you have a probleme here:

in insert(array, array.length -1, i); it should be insert(array, array.length -1, array[i]);

you were inserting array index instead of the value

also you have an array out of bound in array[j + 1] = array[j]; because j start from array.length -1, it should be array[j] = array[j-1]; while j>0

last thing: your rightIndex should be i at each iteration not array.length -1.

Complete code :

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

In insertion sort, we divide the initial unsorted array into two parts; sorted part and unsorted part. Initially the sorted part just has one element (Array of only 1 element is a sorted array). We then pick up element one by one from unsorted part; insert into the sorted part at the correct position and expand sorted part one element at a time.

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

I know I am too late at the party. As you are aware there are several ways to do this but the yellow creature on KA apparently wants us to do it in a particular way. Here's the solution that made it happy:

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;
};