Insertion Sort Function Error

Question

In order to do this, the insert function will need to make room for value by moving items that are greater than value to the right. It should start at rightIndex, and stop when it finds an item that is less than or equal to value, or when it reaches the beginning of the array. Once the function has made room for value, it can write value to the array.

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

Why My this function doesn`t work correctly after I input this array !

var array = [3, 5, 7, 11, 13, 2, 9, 6];

It Shows this result:

insert(array, 4, 2);

2,5,7,11,13,13,9,6

Please click the <> and create a minimal reproducible example — mplungjan
– mplungjan, Commented Aug 15, 2017 at 5:38
2, 3, 5, 7, 11, 13, 9, 6 I want this answer, The question is completely clear — Muhammad Hamza
– Muhammad Hamza, Commented Aug 15, 2017 at 5:40
That was also not clear to me. Please update with expected and actual and create a working snippet — mplungjan
– mplungjan, Commented Aug 15, 2017 at 5:43
Hm, do all of your assertions pass? It is the error occurs, my code do the insertion sort algorithm but somethings wrong here — Muhammad Hamza
– Muhammad Hamza, Commented Aug 15, 2017 at 5:45

ProfDFrancis · Accepted Answer · 2017-08-15 06:05:40Z

5

The line that shuffles items to the right needs editing

Change your line that currently reads:

array[rightIndex + 1] = array[rightIndex];

to read as follows:

array[i + 1] = array[i];

In your code as currently written, the rightIndex'th item is repeatedly being pasted into the rightIndex+1'th position. This is why you are getting two 13s in your result.

So your code is almost right already!

Explicitly check for the beginning of the array

You can change the for loop to ensure you never go left of the start of the array.

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

Inserting the i>=0 && means that when i falls below 0, Javascript knows to end the loop. Otherwise it will attempt to read the element array[-1], which is undefined. Luckily the test will still work, because a comparison of any number (even negative) with "undefined", will be false. But it is much better style to explicitly test for this rather than rely on the quirk of the language. The reason is that if you were to apply the same algorithm in another language, the array[-1] might be an error.

edited Aug 15, 2017 at 6:05

answered Aug 15, 2017 at 5:48

ProfDFrancis

9,4071 gold badge23 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Muhammad Hamza Over a year ago

array[rightIndex + 1] = array[rightIndex]; Its the same as above

Muhammad Hamza Over a year ago

Instead of relying on the array's undefined values at negative indices, can you explicitly check that you're at the beginning of the array? Yeah it works, But this lines comes up, What it says

Jaromanda X Over a year ago

@MuhammadHamza - When you say Its the same as above yes, but array[i + 1] = array[i]; is not - and that change produces your expected output

Muhammad Hamza Over a year ago

How can I explicitly check that I am at the beginning of the array? Instead of relying on the array's undefined values at negative indices ? How ?

Muhammad Hamza Over a year ago

for(var i = rightIndex; i>0 && array[i] > value ; i = i - 1) I enter this line , But the error remains the same

|

user6448640 · Accepted Answer · 2017-08-15 06:04:38Z

inserting value into array works correctly with sorted array, in this case your array is not sorted.

var array = [3, 5, 7, 11, 13, 2, 9, 6];

you need to first sort the array, for that use this

var array = [3, 5, 7, 11, 13, 2, 9, 6];

array = arra.sort(function (a, b) {  return a - b;  });

array = array.sort((a, b) => a - b);

//outputs:  2, 3, 5, 6 , 7, 9, 11, 13

then you can insert into this array as sorted

For that you can try something like this

var array = [2, 3, 5, 6 , 7, 9, 11, 13];
var element = 2;

function insert(element, array) {
   array.push(element);

   array.sort(function(a, b) {
       return a - b;
   });

   return array;
}


//outputs:  2, 2, 3, 5, 6 , 7, 9, 11, 13

Collectives™ on Stack Overflow

Insertion Sort Function Error

2 Answers 2

The line that shuffles items to the right needs editing

Explicitly check for the beginning of the array

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

The line that shuffles items to the right needs editing

Explicitly check for the beginning of the array

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related