Shell-sort algorithm variations in Java

Question

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.

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

Your question seems simple. Where are you struggling to convert these values? You seem aware of Math.pow. You're aware of Math.ceil() correct? Have you tried something that isn't quite working right? — Grambot
– Grambot, Commented Dec 11, 2012 at 21:07
using a ceiling just fixed one of them. My problem is, unless I know where I'm supposed to start, I have no idea what to make of the for loop though for the more advanced onces. — Pat Gallagher
– Pat Gallagher, Commented Dec 11, 2012 at 21:12
I don't know what k in that equation is supposed to be actually. Probably why I'm in trouble here. — Pat Gallagher
– Pat Gallagher, Commented Dec 11, 2012 at 21:16
(3^k - 1)/2 is the formula to give you the gap sequence for the first gap k = 1 for the second gap k = 2 giving you the values in get concrete gap column. — BevynQ
– BevynQ, Commented Dec 11, 2012 at 21:33

Travis Addair · Accepted Answer · 2012-12-11 21:22:47Z

3

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);
        ...
    }

answered Dec 11, 2012 at 21:22

Travis Addair

4274 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

BevynQ · Accepted Answer · 2012-12-11 21:28:20Z

0

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

answered Dec 11, 2012 at 21:28

BevynQ

8,3125 gold badges28 silver badges37 bronze badges