Insertion Sort – Why does the code run correctly for certain sets of values while throws Array Index Out of Bounds Exception for other sets

The code works perfectly fine when first input is the smallest value in the array whereas, for all other cases, the code throws ArrayIndexOutOfBoundsException -1

Test Input1: 6,8,7,11,9 (Works for this input)

Test Input2: 10,9,7,12,1 (Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: -1)

Please share what could be the reason for this and how to resolve this issue.

//SortingMain.java
import java.util.Scanner;

public class SortingMain {

    public static void main(String[] args) {
        int data[] = new int[5];
        Scanner input = new Scanner(System.in);
        InsertionSort obj = new InsertionSort();
        System.out.println("Enter the numbers in array:");
        for(int i=0; i<5;i++) {
            data[i]=input.nextInt();
        }
        obj.insertionSort(data);
        System.out.println("Elements after sorting");
        for(int i=0; i<5;i++) {
            System.out.println(data[i] + " ,");
        }
        input.close();
    }
}
//InsertionSort.java
public class InsertionSort {
    public void insertionSort(int data[]) {
        int i,j,key;
        for(i=1;i<data.length;i++) {
            key=data[i];
            j=i;
            while(data[j-1]>key && j>=1) {
                data[j] = data[j-1];
                j--;
            }
            data[j] = key;
    }
}

Answer

You need to have the condition in your while loop like this: while (j >= 1 && data[j - 1] > key) { ... } i.e. j >= 1 should be checked first and only if this is satisfied, data[j-1] > key should be checked.

This is because first it should be checked that the index I’m going to access from the data is valid and then access it, otherwise IndexOutOfBoundException will occur.

Leave a Reply

Your email address will not be published. Required fields are marked *