CODEWITHSUNDEEP
javaalgorithmsorting
Raghul Gopi
Raghul Gopi

Reputation: 19

Mind numbingly confused with insertion sort

The below code is the standard algorithm for insertion sort.

But playing around with it a bit opened my eyes to something which i cannot wrap my mind around. Any help is much appreciated.

If we replace the variable "Key" with the value arr[i] in this line

if (key < arr[j]), the sorting gets screwed up

can someone explain how this is working.

Thanks

public class InsertionSort {
    public static void main(String[] args) {
        int arr[] = { 100, 12, 31, 56, 4, 39, 2, 1 };
        int temp = 0, j, key;

        for (int i = 1; i < arr.length; i++) {
            j = i - 1;
            **key = arr[i];**
            while (j >= 0) {
                if (key < arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
                j--;
            }
        }
        for (int x : arr) {
            System.out.print("[" + x + "],");
        }
    }
}

Upvotes: 0

Views: 171

Answers (2)

Rahul
Rahul

Reputation: 677

This is because (arr[i] < arr[j]) will be evaluated every time within the while loop. Since, you are shuffling the array elements within loop, arr[i] may change. It should be same for the all the iterations that is why it's value is set to key once outside the loop.

Upvotes: 0

IQV
IQV

Reputation: 500

In the outer loop you have

j = i - 1;

In the inner loop you have

arr[j + 1]

So, when j = i - 1 then it is j + 1 = i. That means when one did not save the original arr[i] in key it is altered during the swap in the inner loop, hence the algorithm is screwed up.

Upvotes: 1

Related Questions