CODEWITHSUNDEEP
javasortingshellsort
Pat Gallagher
Pat Gallagher

Reputation: 83

Shell-sort algorithm variations in Java

Is there a way to calculate the starting point of a for loop and the adjustments to it. The original loop has these conditions

for( int gap = a.length / 2; gap > 0; gap /= 2 )

I adjusted it to set the conditions of the Hibbard's Shell Sort and got this

for( int gap = (int) Math.pow(2, a.length); gap > 0; gap /= 2 )

It works slightly better and might even be right, but I want to work with the more advanced shell sorts from here.

http://en.wikipedia.org/wiki/Shellsort#Gap_sequences

How could I turn (3^k - 1)/2 not greater than the ceiling of n/3 into a for loop condition?

Upvotes: 3

Views: 1258

Answers (2)

BevynQ
BevynQ

Reputation: 8259

for( int gap = 1; gap < ((a.length + 2)/3); gap = (((((gap *2)+1)*3)-1)/2))

Upvotes: 0

Travis Addair
Travis Addair

Reputation: 427

The "k" value is the element of the sequence. So your for loop would probably look something like:

    for (int k = 0; (Math.pow(3, k) - 1) / 2 <= Math.ceil(n / 3); k++) {
        int gap = (int) ((Math.pow(3, k) - 1) / 2);
        ...
    }

Upvotes: 3

Related Questions