3
\$\begingroup\$

I tried to implement the shell-sort algorithm using this Java code:

// Using Pratt sequence 
public static void hSort(int tab[]) {
    int N = tab.length;    
    int k = 0;    
    int sequence = 1;

    // Getting the final term of the pratt sequence 
    while(((int)(Math.pow(3, k) - 1) / 2) < N/3) {
        sequence = (int)(Math.pow(3, k) - 1) / 2;
        k++;
    }     
    k--;

    while(sequence > 0) {
        hInsertionSort(tab, sequence);
        k--;
        sequence = (int)(Math.pow(3, k) - 1) / 2;
    }
}

// H sorting using insertion sort 
public static void hInsertionSort(int[] tab, int h) {
    int N = tab.length;
    int k = 0;
    while (k < h) {
        for (int i = k; i < N; i+=h) {
            for (int j = i; j > k+h-1; j-=h) {
                if (less(tab[j], tab[j-h]) == -1) exch(tab, j, j-h);
                else break;
            }
        }
    k++;
    }
}

You can use the hsort method to try sort a table of integers.

Is the complexity of this implementation the same as the usual implementation?

\$\endgroup\$
1
  • \$\begingroup\$ (Without a motivation anywhere in the code, h looks an ill-chosen name.)(doc-comment your java-code.) In hInsertionSort(int[] tab, int h), you use a while-loop around two for-loops; from outer to inner loop, the iteration variables read k, i, j: why? In the inner loop, I'd write if (less(tab[j], tab[j-h]) != -1) break, followed by an "unconditional" exchange. \$\endgroup\$ Commented Aug 29, 2017 at 4:50

2 Answers 2

Reset to default
1
\$\begingroup\$ 
    int N = tab.length;    
    int k = 0;

These lines (and others) have trailing whitespace. It's a good habit to learn to avoid that (and even to set the IDE up to automatically eliminate it) because avoiding it will reduce revision control diffs which just change the amount of trailing whitespace.

    int sequence = 1;

    // Getting the final term of the pratt sequence 
    while(((int)(Math.pow(3, k) - 1) / 2) < N/3) {
        sequence = (int)(Math.pow(3, k) - 1) / 2;
        k++;
    }     
    k--;

So right now ((int)(Math.pow(3, k + 1) - 1) / 2) >= N/3. That means k = Math.floor(Math.log(N/3*2 + 1) / Math.log(3)); modulo any out-by-one errors. It's worth writing a few test cases, but you should be able to eliminate the while loop entirely.

    while(sequence > 0) {
        hInsertionSort(tab, sequence);
        k--;
        sequence = (int)(Math.pow(3, k) - 1) / 2;
    }

In terms of the previous sequence, we have sequence = (((2 * sequence + 1) / 3) - 1) / 2;; that can be simplified exactly to (sequence - 1)/3, and using integer arithmetic to just sequence /= 3;

// H sorting using insertion sort 
public static void hInsertionSort(int[] tab, int h) {

Is there any reason for this to be public?

        for (int i = k; i < N; i+=h) {
            for (int j = i; j > k+h-1; j-=h) {

Is there any reason for not having whitespace around += and -=? It seems inconsistent.

                if (less(tab[j], tab[j-h]) == -1) exch(tab, j, j-h);

I would prefer < 0 to == -1 here because it's more consistent with the way Java's Comparable and Comparator work. Although I'm not entirely sure why there's a less method to compare two integers in the first place.

    k++;
    }

What happened to the indentation here?

Is the complexity of this implementation the same as the usual implementation?

What do you consider to be the usual implementation? How does this one differ? If it's just the step size sequence, I was under the impression that this one is the usual one; and as to complexity, the complexity of shell sort with different sequences is such a hard problem that there are still potential doctorates in it.

\$\endgroup\$
1
\$\begingroup\$

Yes.
It is the same complexity.

\$\endgroup\$

You must log in to answer this question.