Thread: Shell Sort Comparisons and Exchanges

Im trying to count the comparisons and exchanges it take for Shell sort to sort a array of numbers 1-10. with the comparison counter where is is now (comp) and the exchange counter where it is (exch) im getting 22 comparisons and zero exchanges. i believe the zero exchanges is right because its obviously a sorted array so no exchanges are needed. with a array of 10 elements i dont think 22 comparisons would be correct. can someone show me where these expressions need to be and explain why? i would greatly appreciate it.

public static void shellSort(int[] array) {
        int interval = array.length / 2;
        int comp = 0, exch = 0;
        while (interval != 0) {
            for (int i = 0; i < interval; i++) {
                for (int p = i + interval; p < array.length; p += interval) {
                    int key = array[p];
                    int j = p - interval;
                    while (j >= 0) {
                        comp++;         //Comparison here
                        if (key < array[j]) {
                            array[j + interval] = array[j];
                        } else
                            break;
                        exch++;     //Exchange here
                        j -= interval;
                    }
                    array[j + interval] = key;
                }
            }
            interval /= 2;
        }

i dont think 22 comparisons would be correct.

Why? Add some print statements that print out the values being compared so you can judge if the count is correct.

but shouldn't it make 9 comparisons

I don't know sorting theory and can't comment on the algorithm you are testing.
I suspect some very smart people developed the algorithm.

Did you try adding a print statement to show what was being compared?

--- Update ---

Also posted at: https://stackoverflow.com/questions/...l-sort-program

Please read: http://www.javaprogrammingforums.com...s-posting.html