0

Below is my code for Insertion Sort and i am facing an exception of array indexing.

import java.util.Scanner;

public class Insertion_Sort {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=4;
        int ar[]=new int[n];
        for(int i=0;i<n;i++)
        {
            ar[i]=sc.nextInt();
        }
        for(int i=1;i<n;i++)
        {
            int c=ar[i];
            int j=i-1;
            while(ar[j]>ar[j+1] && j>=0)
            {
                ar[j+1]=ar[j];
                j--;
            }
            ar[j+1]=c;
            
        }
        for(int i=0;i<n;i++)
        {
            System.out.println(ar[i]);
        }
        

    }

}

This is the exception i am getting everytime i run this

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 4
    at dfsd.Insertion_Sort.main(Insertion_Sort.java:17)
bob
  • 2,674
  • 1
  • 29
  • 46
Swapnil
  • 1
  • 2
    The error is telling you exactly what's wrong. How can you access position -1 of an array? – sleepToken Feb 21 '21 at 18:20
  • 3
    Specifically, can you think of a time when `while(ar[j]>ar[j+1] && j>=0)` could cause a problem? `j>=0` will *not* be checked first. – sleepToken Feb 21 '21 at 18:23
  • Which line is line 17? Please don't hide information that is needed for debugging. – NomadMaker Feb 21 '21 at 18:33
  • @Swapnil The cause of error is that you have to use `while (j >= 0 && ar[j] > ar[j+1])`. This is necessary. Check here for more information: https://stackoverflow.com/questions/8759868/java-logical-operator-short-circuiting – AKSingh Feb 21 '21 at 18:33
  • @Swapnil You have also used incorrect logic for `insertion sort`. After making the necessary change in `while` loop, the resultant output will be wrong. Do correct it. – AKSingh Feb 21 '21 at 18:35

2 Answers2

0

First thing is that you should check j >= 0 first and if that happen check second condition which is ar[j] > ar[i]. but there is another problem ar array is changing during the process and you should use c instead of ar[i] so the condition would be: j >= 0 && ar[j] > c. Here is the working version of your code:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = 4;
    int ar[] = new int[n];
    for (int i = 0; i < n; i++) {
        ar[i] = sc.nextInt();
    }
    for (int i = 1; i < n; i++) {
        int c = ar[i];
        int j = i - 1;
        while (j >= 0 && ar[j] > c) {
            ar[j + 1] = ar[j];
            j--;
        }
        ar[j + 1] = c;

    }
    for (int i = 0; i < n; i++) {
        System.out.println(ar[i]);
    }

}
Tashkhisi
  • 2,070
  • 1
  • 7
  • 20
-1

J>=0 should be the first condition. Also you need to check j<n as you are using j+1 in the check (scenario when i reached n-1) to avoid exceptions. The logic of insertion sort seems to be incorrect.

Kishore Rajendran
  • 1
  • 2