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,,

Is there a reason why you're re-implementing `sort` when you can just do `var array = [22, 11, 99, 88, 9, 7, 42].sort(function(a, b) { return a > b; });`? — vrmc, Jun 08 '15 at 15:42
yes the reason being is im trying to implement an algorithm for academic knowledge. Im well aware I could do it this way just for practical purposes. I want to get better at algorithms. — , Jun 08 '15 at 15:43
Im messing up when I call ```insert(array, array.length -1, i)``` and I know I need to change those last two parameters based on me messing around with it. Insert function is correct. — , Jun 08 '15 at 15:44
What you really need is to learn debugging: put this code in a js file, access it with Chrome and use Chrome Developer Tools to put a breakpoint or console.log to see where variables are not what you expect. — Iftah, Jun 08 '15 at 15:51
thank you for the comment, but I am aware where the problem is, I just dont know what to put into the function to make it work. Isnt the whole point of stackoverflow to get direct responses instead of deflecting comments like this one? — , Jun 08 '15 at 15:53

score 2 · Answer 1 · answered Feb 12 '16 at 05:11

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 &lt; array.length-1; i++){
        insert(array, i, array[i+1]);
    }
};

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

yahya el fakir · Accepted Answer · 2015-06-08T16:13:12.213

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

that was my initial thought but I have tried this solution and khan academy rejects it! — , Jun 08 '15 at 15:48
What was interesting is khan academy essentially gave me the insert fx for this question, so I never thought to check it for accuracy. Your description shed a lot of light on the issue and hopefully will be helpful for future people who get stuck on this track. — , Jun 08 '15 at 16:18

score 0 · Answer 3 · answered Jun 19 '16 at 10:13

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

score 0 · Answer 4 · answered Sep 19 '16 at 07:25

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

Insertion Sort help in javascript -- Khan Academy

4 Answers4