Insertion Sort from Right to left with Javascript

Question

I am trying to write an insertion sort function that works from right to left. Not in descending order. I just am not understanding why this code would not properly sort numbers.

function reverseInsertionSort(arr) { 
for(var i = arr.length -1; i >0; i--) 
var val = arr[i];
    var j;
    for(j = i; j > 0 && arr[j-1] < val; j--) {
        arr[j-1] = arr[j]; }
     va=arr[j]; }
function insertionSort(arr) { 
    for(var i = 1; i < arr.length; i++) { 
        var val = arr[i];
        var j;
        for(j = i; j > 0 && arr[j-1] > val; j--) {
            arr[j] = arr[j-1]; }
        arr[j] = val; }
    }
            arr[j] = val;
        }
    }
var length = Math.floor(Math.random()*100)+1;
var arr = new Array();
for(let i = 0; i < length; i++) {
    arr.push(Math.floor(Math.random()*10000)+1);
}
var arr2= arr.slice();

reverseInsertionSort(arr2);
console.log(arr2)

It is not sorted, and the output ends in undefined. arr is being used to test the insertionsort fun Happy to accept constructive criticism.

Possible duplicate of Insertion Sort Algorithm on JavaScript — Kamalesh M. Talaviya
– Kamalesh M. Talaviya, Commented Feb 7, 2019 at 5:12
i have an insertion sort. it works normally and goes from left to right. I am trying to do the same thing but from the other end of the array — William Machado
– William Machado, Commented Feb 7, 2019 at 5:18
Since you said criticism is welcome... this kind of code looks minified to me. Scary, will never review them. maybe make those single char variable more descriptive. 1 or 2 lines of comment to state certain behaviour or reason for having the code would be nice — Samuel Toh
– Samuel Toh, Commented Feb 7, 2019 at 5:18

Sankha Karunasekara · Accepted Answer · 2019-02-07 06:25:29Z

3

This will work.

function reverseInsertionSort(arr) { 

    for(var i = arr.length-2; i>=0; i--) {

        var value = arr[i];
        var j;

        for(j = i; ((j < arr.length) && (arr[j+1] > value)); j++){ 
            arr[j] = arr[j+1]; 
        } 
        arr[j] = value;
    }
    return arr;
}

//test
var inputArray = [3,2,4,5,1,10,23];
var resultArray = reverseInsertionSort(inputArray);
console.log(resultArray); //[23, 10, 5, 4, 3, 2, 1]

answered Feb 7, 2019 at 6:25

Sankha Karunasekara

1,72619 silver badges22 bronze badges

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

3 Comments

William Machado Over a year ago

I see. We want to start 2 before the end so that we can compare the last with the second to last on the first run through. Thank you very much.

William Machado Over a year ago

This sorts in descending. I need to sort in ascending. Flipped the sign on arr[j+1]>val and it worked like a charm :D

Sankha Karunasekara Over a year ago

1) I started from 2 last element just to demostrate logic behind insertion sort more clearly. It should work as the same even if we use arr.length-1. 2) I am glad that I left it for you to figure it out. 😉

SSG · Accepted Answer · 2019-02-07 06:28:02Z

1

You should start the outer loop from the last element ie. len-1. The undefined member of the array is created due to your outer loop starting from arr.length . Try this :

function insSort(arr){
  for(var i=arr.length-1;i>=0;i--){
    key=arr[i];
    j=i+1;
    while(j<arr.length&&arr[j]<=key){
      arr[j-1]=arr[j];
      j++;
    }
    arr[j-1]=key;
  }
}
var length = Math.floor(Math.random()*100)+1;
var arr = new Array();
for(let i = 0; i < length; i++) {
    arr.push(Math.floor(Math.random()*10000)+1);
}
console.log(arr);
insSort(arr);
console.log(arr);

edited Feb 7, 2019 at 6:28

answered Feb 7, 2019 at 5:23

SSG

1207 bronze badges

3 Comments

William Machado Over a year ago

It is still out of order with those changes

code  function reverseInsertionSort(arr) {  	for(var i = arr.length -1; i >0; i--)  	var val = arr[i]; 		var j; 		for(j = i+1; j > 0 && arr[j-1] < val; j--) { 			arr[j-1] = arr[j]; } 		 va=arr[j]; }

William Machado Over a year ago

Even plugging your code in directly results in an incorrectly sorted array.

SSG Over a year ago

I've updated the code. Try that . Codepen : codepen.io/Sarthak_SG/pen/OdOEMG

mohd jagir · Accepted Answer · 2024-09-12 23:28:47Z

0

        //descending order
        function insertionSortDesc(arr) {
            for (let i = 1; i < arr.length; i++) {
                let numberToInsert = arr[i];
                let j = i - 1;
                while (j >= 0 && arr[j] < numberToInsert) {
                    arr[j + 1] = arr[j];
                    j = j - 1;
                }
                arr[j + 1] = numberToInsert
            }
            return arr;
        }
        let arr = [20, -6, 8, -2, 4];
        console.log(insertionSortDesc(arr));
        
        //ascending order
             function insertionSortAsc(arr) {
            for (let i = 1; i < arr.length; i++) {
                let numberToInsert = arr[i];
                let j = i - 1;
                while (j >= 0 && arr[j] > numberToInsert) {
                    arr[j + 1] = arr[j];
                    j = j - 1;
                }
                arr[j + 1] = numberToInsert
            }
            return arr;
        }
        let arrData = [-5, 2, 10, 11, 6, 15, 7];
        console.log(insertionSortAsc(arrData));

edited Sep 12, 2024 at 23:28

answered Sep 12, 2024 at 23:11

mohd jagir

11 bronze badge

1 Comment

m-sarabi Over a year ago

Thanks. Your answer could use some commentary and explanation.

Collectives™ on Stack Overflow

Insertion Sort from Right to left with Javascript

3 Answers 3

3 Comments

3 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related