CODEWITHSUNDEEP
javaalgorithmsortinginsertion-sort
monsteraflam
monsteraflam

Reputation: 39

Writing an algorithm for insertion sort in java

I'm trying to implement insertion sort in Java. I think something isn't quite right with my code.

public int[] sort(int[] unsorted) {
    int i, j, v;
    for (i = 1; i < unsorted.length - 1; i++) {
        v = unsorted[i];
        j = i;

        while (unsorted[j-1] > v && j >= 1) {
            unsorted[j] = unsorted[j -1];
            j--;
        }
        unsorted[j] = v;
    }
    return unsorted;
}

I get an IndexOutOfBoundsException for my while loop ([j-1]). But how can I rewrite the code so it actually works?

Upvotes: 1

Views: 142

Answers (1)

biqarboy
biqarboy

Reputation: 852

For index i, you can simply start the index j from i-1. And in the while loop, always put the index validity check first, before accessing data from that index. The following code solves your problem:

public int[] sort(int[] unsorted) {
    int i, j, v;
    for (i = 1; i < unsorted.length; i++) {
        v = unsorted[i];
        j = i - 1;

        while (j >= 0 && unsorted[j] > v) {
            unsorted[j + 1] = unsorted[j];
            j--;
        }
        unsorted[j + 1] = v;
    }
    return unsorted;
}

Upvotes: 2

Related Questions