I am mindboggled. Insertion Sort (basic sort, i know) algorithm is doing something I can't explain

user_19412479 0
Viewed 57

Ok, hear me out. Here is my code for insertion sort.

        for (int i = 0; i < arr.length; i++) {
            T curr = arr[i];
            int i2 = i - 1;
            // if (i2 == -1) {
            //     System.out.println("yes");
            //     break;
            // } 
            while (i2 >= 0 && comparator.compare(arr[i2], curr) > 0) {
                arr[i2 + 1] = arr[i2];
                i2--;
            }
            arr[i2 + 1] = curr;
        }

So, as of right now, I have

if (i2 == -1) {
    sout("yes");
    break;
}

because I wanted to skip the iteration where i2 will obviously be equal to -1 and thus not have a single effect on the array because the first iteration does nothing and keeps the first element in the 0 position of the array because that is exactly how insertion sort works.

Now, I'm not exactly sure what's going on, because, as this aforementioned if statement is commented out, the algorithm works exactly as expected. BUT, when I un comment it, the algorithm fails.

What I don't understand is how commenting it out, or not including this if statement at all, leads to a failing algorithm, because no matter what, when i2 == -1, there is literally, as far as I can tell, no effect on the algorithm, since, when i2 is -1, and the if statement described is omitted, the while loop does not execute, and the arr[i2 + 1] = curr statement DOES execute, but it will just keep the first element in its place, EXACTLY how the presence of the if statement keeps the first element in its place because it breaks the loop and does not alter a single thing.

I'm not sure if I'm absolutely insane and missing something inexplicably clear to a sane person, but I literally see not a single way that the omission or inclusion of the if statement described changes anything about the code, especially since i2 will only be -1 on the first iteration of the for loop.

Thank you very much.

insertion-sort java
1 Answers

You should replace break with continue.

Because, at the first iteration, it will always be -1 and it will break the for loop, which means there are no further iterations.

continue is the right weapon.

if (i2 == -1) {
    sout("yes");
    continue;
}

The above code will skip the 1st iteration, while your code will terminate the for loop.

But, there is no need of this if block because you are already filtering out 1st iteration in the condition of while loop.

user_140488160
Related