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?

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

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;