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];
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.
arr[2] = arr[pos-1]
.pos
is decreasing to pos == 1
.arr[2] = arr[1-1]
means arr[2] = arr[0]
.while
loop is true.arr[1] = arr[pos-1]
.pos
is decreasing to pos == 0
.arr[1] = arr[0-1]
means arr[1] = arr[-1]
.ArrayIndexOutOfBounds
).Corrected code is like this. (Line number 9)
arr[pos--] = arr[pos];
or
arr[pos] = arr[--pos];