Why is this method of insertion sort not working?

Question

In this insertion sort technique, in the while loop condition when I compare current and arr[j], the program works but if I compare arr[i] with arr[j] the program doesn't give the correct output.
Do you have any idea there's a difference although current and i are same?

void insertionSort(int arr[], int s){
    for(int i=1;i<s;i++){
        int current = arr[i];
        int j=i-1;
        while(arr[j]>current && j>=0){// if I use arr[i] instead of current the program gives wrong output.
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = current;
        printArray(s, arr);
    }
}

If you look carefully, you can notice that if the while loop does more than one iteration, it will not compare the same value on second iteration as arr[i]is modified by the line arr[j + 1]. You set j to i - 1 the then modify arr[j + 1] which is the location of arr[i]since j == i - 1 implies that j + 1 == i. You can also use a debugger to follow the program step by step. — Phil1970
– Phil1970, Commented Mar 16, 2021 at 1:58
Review the order of the two tests in arr[j]>current && j>=0. — chux
– chux, Commented Mar 16, 2021 at 2:16

Antonin GAVREL · Accepted Answer · 2021-03-16 01:53:25Z

1

They are not the same because you are making operations on the array arr in your while loop, through index i, and potentially writing a new value into array[i] when j+1 == i, that is why you need to save the current value of arr at index i before the while loop.

answered Mar 16, 2021 at 1:53

Antonin GAVREL

11.4k12 gold badges62 silver badges92 bronze badges

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

Collectives™ on Stack Overflow

Why is this method of insertion sort not working?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related