Implementing Insert Function

Question

I am currently working through Khan Academy's algorithm course, which uses JS to teach fundamental algorithms. I am currently in the process of implementing an insertion sort, but have found a problem.

We are writing a function which takes in an array, index to start from and value, in order to insert a number in the correct ordered position. I have written said function here:

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

This works fine, and performs as it should, however it does not pass KA's automated marking system. They give guidelines for the code and suggest it be done as such:

for(var ____ = _____; ____ >= ____; ____) {
 array[____+1] = ____;
}
____;

Does anyone know how I could reiterate my code to conform to these standards?

• wvdz: I'd say it makes more sense to ask it on that site.

Answer 1

I had a similar solution as you and didn't pass their automated test. If you look later at "Challenge: Implement insertion sort" they actually go ahead and implement the function for you:

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

As an aside, the reason you don't need to declare j before the for loop (to be used later) is because JavaScript doesn't have block scope (TIL): See here

Answer 2

From the challenge:

Although there are many ways to write this function, you should write it in a way that is consistent with the hint code.

It's strictly checking for this:

var ___;
for(___ = ___; ___; ___) {
 array[___ + 1] = ___;
} 

So even though these two alternates are correct:

while(array[rightIndex] > value && rightIndex >= 0) {
 array[rightIndex + 1] = array[rightIndex];
 rightIndex--;
}
array[rightIndex + 1] = value;

And especially this almost identical one (switched the middle statement in the for loop):

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

This one is the answer:

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

Ironically, it doesn't care about the useless first variable in the hint...

var ___;

Answer 3

No need to return the array, as it is passed by reference. Just shift every element by 1 to the right. The last statement just inserts the value at the correct position.

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

• derMrich: @Bergi I agree, but then it would not fit into his code template. I don't think such templates are useful in any ways because there will always be better solutions which are not fitting into such a template. Furthermore students are discouraged to search for other solutions.
• Felix: I think that array[rightIndex] = value; is wrong.
• Alejandro: You are @Felix , this is wrong. He must have meant array[i] inside the for scope

Answer 4

Most of the answers posted here are correct. But It does not get us to next step in Khan Academy. It could be because Khan Academy expects a certain variable name, indent settings etc. I am not exactly sure why It does not get us to next step.

This code helped me go to next step:

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

Before I discovered this code, I used i as variable name instead of j, but it did not get me to next step. But this does.

Answer 5

This has worked:

var insert = function(array, rightIndex, value) {

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