Hibbard's Shell Sort
I have gotten down shell sort algorithms, but i just cant get Hibbard's increments. I get what they are, I just cant implement them into my basic shell sort. For other shell sorts, they go while gap>0, but with Hibbard it's counting up... when does it stop?? i figure if it goes while gap<array.length, the gap will eventually over shoot the end of the array?? please help!!
I just checked out the wikipedia page on it and from this pseudocode
I'm assuming is the basis of what you're working with. Hibbard's sequence is 2x+1 all the way from 1 to array.length correct?
input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2.2)
If you're going while gap < array.length and incrementing up then it should stop before you reach an index out of bounds.
yeah I tried doing it while gap<array.length but it would only work for very small array sizes (<1000) and would take very long. >1000 would not even work. I ended up just figuring out a high point to start at and working my down, and that worked fine. thanks for the reply.