Search code examples
javaarraysalgorithmdata-structuresinsertion-sort

Why I cannot use array index decrement when using a another array value in Java?


This is a simple code for Insertion Sort in Java. I tried reducing the lines of my Java code. But it cannot be done with this issue. I want to know why it cannot be done.

Code that I have tried (error happens in line number 9)

import java.util.Scanner;

public class InsertionSortModified {
    public static int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int pos = i;
            while (pos > 0 && arr[pos-1] > temp)
                arr[pos--] = arr[pos-1];
            arr[pos] = temp;
        }
        return arr;
    }

    public static void main(String args[]) {
        Scanner scnr = new Scanner(System.in);
        int elementarr[] = new int[5];

        for (int j = 0; j < 5; j++)
            elementarr[j] = scnr.nextInt();
        
        elementarr = insertionSort(elementarr);
        for (int j = 0; j < elementarr.length; j++)
            System.out.print(elementarr[j] + " ");
    }
}

Error showing in the command window

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
        at InsertionSortModified.insertionSort(InsertionSortModified.java:9)
        at InsertionSortModified.main(InsertionSortModified.java:22)

Program is working when the code modified to like this. (Line number 8 to 11)

            while (pos > 0 && arr[pos-1] > temp) {
                arr[pos] = arr[pos-1];
                pos--;
            }

Why I cannot use

arr[pos--] = arr[pos-1];

Solution

  • I have found what the problem is. Step by step execution of the code is here.

    Line number 9:

    When i == 2, pos == 2. At the line 9 execution order is like this.

    1. At initially first execution if the while loop, arr[2] = arr[pos-1].
    2. Positioning the array index 2. But after positioning pos is decreasing to pos == 1.
    3. Then line becomes to this arr[2] = arr[1-1] means arr[2] = arr[0].
    4. After that still while loop is true.
    5. Then the second execution of the while loop at initially arr[1] = arr[pos-1].
    6. Then positioning the array index 1. But after positioning pos is decreasing to pos == 0.
    7. Then line becomes to this arr[1] = arr[0-1] means arr[1] = arr[-1].
    8. So error happens in here. (ArrayIndexOutOfBounds).

    Corrected code is like this. (Line number 9)

    arr[pos--] = arr[pos];
    

    or

    arr[pos] = arr[--pos];