error in insertion sort code

Question

I am trying to print the steps of the insertion sort algorithm

I wrote it in c++ before & it worked very good, but when I converted into Java, it gave me this error

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at insertion.insertion_sort(insertionSort.java:45)
at insertionSort.main(insertionSort.java:8)

and this is my code :

    /* print the steps of insertion sort algorithm */

class insertionSort {

    public static void main(String[] args) {

        insertion obj = new insertion();
        obj.insertion_sort();

    } // end of main function

} // end of insertionSort class

class insertion {

    int A[] = { 5, 8, 9, 1, 0, 4, 7, 3, 6, 2 };
    final int ELEMENTS = 10;

    void printStep(int source, String destination) {
        System.out.print("move array[" + source + "]  -----> " + destination);
    }

    void printStep(int source, int destination) {
        System.out.print("move array[" + source + "]  -----> " + "array["
                + destination + "] ");
    }

    void printStep(String source, int destination) {
        System.out.print("move " + source + " -----> array[" + destination
                + "] ");
    }

    void insertion_sort() {

        int key, i;

        for (int j = 1; j < ELEMENTS; j++) {
            key = A[j];
            printStep(j, "key");
            System.out.println();
            i = j - 1;

            while (A[i] > key && i >= 0) {
                A[i + 1] = A[i];
                printStep(i + 1, i);
                System.out.println();
                i = i - 1;
            }

            A[i + 1] = key;
            printStep("key", i + 1);
            System.out.println();
            System.out.println("======================================");

        }

    } // end of insertion_sort ( )

} // end of insertion class

plz someone explain where is my wrong?

Arrays start with 0 as an index. Change j=1 to j=0 in for loop. — Parvin Gasimzade, Dec 08 '12 at 15:45
Have you at least debugged the code to find the errors? We're not a free service to do the debug for you. — Luiggi Mendoza, Dec 08 '12 at 15:46
`for(int j = 1; j < ELEMENTS; j++)` should be `for(int j = 0; j < ELEMENTS; j++)` — Fahim Parkar, Dec 08 '12 at 15:46

score 4 · Accepted Answer · edited May 23 '17 at 12:29

4

The problem is in your while validation

while(A[i] > key && i >= 0)

You must check the i value before A[i]

while(i >= 0 && A[i] > key)

Further explanation: Note that inside this while loop you're deduct the value of the i variable. So there will be a time when i will be less than 0, and you're checking A[-1] before checking i >=0. The order of the validations in while and if sentences matters, Java evaluates them from left to right.

More info:

Boolean expression order of evaluation in Java?

edited May 23 '17 at 12:29

Community

1
1

answered Dec 08 '12 at 15:49

Luiggi Mendoza

85,076
16
154
332

Why would he get away with this in C++? Because of undefined evaluation order and luck? – Esailija Dec 08 '12 at 15:52

error in insertion sort code

1 Answers1