CODEWITHSUNDEEP
calgorithmsortingshellsort
overexchange
overexchange

Reputation: 1

h-sorting in Shell sort

In shell sort, 3h+1 sequence is recommended to h-sort a list using insertion sort

//1, 4, 13, 40, ...

Optimal formula to compute start value of h is one-third of listsize, as shown below,

int h = 1;
while(h < listSize/3){ // why N/3?

  h = 3*h + 1
}
while(h >= 1){

  //h-sort the array
  // perform insertionSort
  h = h/3;
}

Question:

To perform shell sort, How to prove mathematically that h(at max) should be less than listSize/3?

Upvotes: 1

Views: 1757

Answers (2)

Harshad Sharma
Harshad Sharma

Reputation: 111

The optimal sequence that is recommended for Shell sort is called a Knuth Sequence and what it actually is 3h+1 with h starting from 0 and is replaced by the solution of the previous equation.

h=0;    3*0+1=1
h=1;    3*1+1=4
h=4;    3*4+1=13
h=13;   3*13+1=40 and so on.

now for Shell sort, it is recommended that you follow this sequence in the reverse order when choosing the optimal "gap". To do that, you have to find the last "gap" which is lesser than the listsize.

Imagine your list is of size n=100, then you want gaps to be 40,13,4,1

int gap;
for(int h=0; h<n; h=h*3+1)
    gap=h;

this will get you to 40. Now you do your Insertion Sort and you get to the previous gap value as gap=gap/3 technically gap=(gap-1)/3 but since the remainder is discarded, we don't worry about it.

So you get the final code of something like:

for(int h=0; h<n; h=h*3+1)
    gap=h;

while(gap>=1)
{
    //insertion sort with gap increments
    gap=gap/3;
}

Upvotes: 3

MBo
MBo

Reputation: 80287

If we continue to increase h after condition (h < listSize/3), h becomes larger than listSize, and there is no sense in h-sorting - we cannot compare items A[i] and A[i+h] because the second index is beyond list range.

Upvotes: 3

Related Questions