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

• Anonymous: What's happening that you don't want?
• vrmc: 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; });?
• user3366804: 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.
• Iftah: 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.
• user3366804: 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?

Answer 1

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 2

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

• user3366804: that was my initial thought but I have tried this solution and khan academy rejects it!
• user3366804: 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.

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