CODEWITHSUNDEEP
javaalgorithmsortinginsertion-sort
KeironO
KeironO

Reputation: 179

What's wrong with my insertion sort?

I'm trying to sort a large datafile using an Insertion-based sorting algorithm, the code runs fine but the output is incorrect. I've studied it over and over to absolutely no avail, can anyone see where I've gone wrong?

public void sort(Comparable[] items) {
    for (int i = 1; i < items.length; i++) {
        Comparable temp = items[i];
        int j = i - 1;
        while (j >= 0 && items[j].compareTo(items[j]) > 0) {
            items[j + 1] = items[j];
            j = j - 1;
        }
        items[j] = temp;
    }
}

An example datafile I have produced is...

2
1
3
5
9
6
7
4
8

And obviously the output should be 1,2,3,4... - but instead I get 1 3 5 9 6 7 4 8 8

Upvotes: 1

Views: 130

Answers (2)

Bernhard Barker
Bernhard Barker

Reputation: 55589

items[j].compareTo(items[j]) should be items[j].compareTo(temp), otherwise you're just comparing the item against itself - you need to be comparing it against the object you want to insert.

Then items[j] = temp; will also cause an ArrayIndexOutOfBoundsException because, at the end of the loop, items[j] is smaller than temp, or j == -1, so we need to insert at the position after that - the simplest fix is just changing that to items[j+1] = temp;.

Upvotes: 5

Mr. Polywhirl
Mr. Polywhirl

Reputation: 48600

Algorithm:

for i ← 1 to length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1

Translated to Java:

import java.util.*;

class InsertionSortTest {
    public static int[] insertionSort(int[] A) {
        for (int i = 1; i < A.length; i++) {
            int j = i;
            while (j > 0 && A[j-1] > A[j]) {
                int t = A[j];
                A[j] = A[j-1];
                A[j-1] = t;
                j--;
            }
        }
        return A;
    }

    public static void main (String[] args) {
        int[] arr = { 5, 3, 0, 2, 1, 4 };

        System.out.println(Arrays.toString(insertionSort(arr)));
    }
}

Upvotes: 0

Related Questions