CODEWITHSUNDEEP
javaalgorithmsortinginsertion-sort
John
John

Reputation: 857

Insertion sort, number of comparisons

Hi all for an assignment we must count the number of comparisons for a number of algorithms. I'm using the code in the book "Algorithms" by Sedgewick & Wayne. I don't see where my code is wrong actually... As soon we going to compare something I count my comparison...

public long sort(Comparable[] a) {
        if (a == null) {
            throw new IllegalArgumentException("argument 'array' must not be null.");
        }
        int N = a.length;
        for (int i = 0; i < N; i++) {
            for (int j = i; j > 0; j--) {
                this.comparisons++;
                if(less(a[j], a[j-1]))
                    exch(a, j, j-1);      
            }
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
        return this.comparisons;
    }

the less method which I use:

private boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

It must pass this test 

Integer[] array = {4, 2, 1, 3, -1};
        Comparable[] arrayClone1 = array.clone();
        Comparable[] arrayClone2 = array.clone();
        long nbCompares1 = i.sort(arrayClone1);
        long nbCompares2 = i.sort(arrayClone2);
        System.out.println("1" + nbCompares1);
        System.out.println("2" + nbCompares2);

those two should be equal....

The isSorted methods:

 private boolean isSorted(Comparable[] a) {
        System.out.println("here");
        return isSorted(a, 0, a.length - 1);
    }

    // is the array sorted from a[lo] to a[hi]
    private boolean isSorted(Comparable[] a, int lo, int hi) {
        System.out.println("here1");
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

Someone ideas about this? Help will be appreciated!

Upvotes: 1

Views: 11098

Answers (1)

esin88
esin88

Reputation: 3209

Number of comparisons should be exactly N*(N-1)/2. Maybe you mess with comparisons field in somewhere else, so I would advise to use local variable instead:

public long sort(Comparable[] a) {
        if (a == null) {
            throw new IllegalArgumentException("argument 'array' must not be null.");
        }
        int N = a.length;
        int comparisonsCount = 0; // use this instead
        for (int i = 0; i < N; i++) {
            for (int j = i; j > 0; j--) {
                comparisonsCount++; // edit here
                if(less(a[j], a[j-1]))
                    exch(a, j, j-1);      
            }
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
        return comparisonsCount; // and here
    }

Upvotes: 1

Related Questions