CODEWITHSUNDEEP
javaalgorithmsortinginsertion-sort
Junaid Arshad
Junaid Arshad

Reputation: 68

Why can't we change the order of statements in insertion sort's while loop?

As shown below is the basic insertion sort algorithm taught at school. if you change the order of while loop parameters, it doesn't work.

public static int[] insertionSort(int[] A){
    for(int i =1; i<A.length;i++){
        int key = A[i];
        int j = i;
        while(j>0&&A[j-1]>key){
            A[j]=A[j-1];
            j--;
        }
        A[j]=key;
        }       
    return A;
}

After the change (Now the code wont work and it will give java.lang.ArrayIndexOutOfBoundsException: -1 expection):

public static int[] insertionSort(int[] A){
    for(int i =1; i<A.length;i++){
        int key = A[i];
        int j = i;
        while(A[j-1]>key&&j>0){
            A[j]=A[j-1];
            j--;
        }
        A[j]=key;
        }       
    return A;
}

If there any other way to implement the same algorithm so that the order of the conditional loop statements doesn't matter?

Upvotes: 2

Views: 397

Answers (2)

Nidhi Grover Raheja
Nidhi Grover Raheja

Reputation: 1

You can improve the above code as follow. Now the while loop will never fail for arr[-1] condition as every time j==-1 the loop will break out.

public static void InsertionSort()
    int j, temp;
    Scanner sc = new Scanner(System.in);
    System.out.println("enter the size");
    int n = sc.nextInt(); 
    int arr[] = new int[n];
    System.out.println("enter the elements");
    for (int i = 0; i < n; i++)
    {
        arr[i] = sc.nextInt();
    }
    for (int i = 1; i < n; i++)
    {
        temp = arr[i]; 
        j = i - 1;
        while (arr[j] > temp && j >= 0)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
            if (j == -1)
                break;
        }
        arr[j + 1] = temp;
    }
    System.out.println("Array Sorted through Insertion Sort");
    for (int i = 0; i < n; i++)
    {
        System.out.println(arr[i]);
    }
}

Upvotes: -1

SLaks
SLaks

Reputation: 887777

Because of short-circuit evaluation.

If the first half of an && is false, the second half will not be evaluated at all (since the result cannot possibly be true).
Therefore, you can write j > 0 && A[j - 1]..., and A[j - 1] will only be evaluated if j > 0.

Upvotes: 5

Related Questions