shell sort sequence implementation in C++

Question

I am reading about shell sort in Algorithms in C++ by Robert Sedwick.

Here outer loop to change the increments leads to this compact shellsort implementation, which uses the increment sequence 1 4 13 40 121 364 1093 3280 9841 . . . .

template <class Item>
void shellsort(Item a[], int l, int r)
{
    int h;
    for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);
    for (; h > 0; h = h / 3)
    {
        for (int i = l + h; i <= r; i++)
        {
            int j = i; Item v = a[i];
            while (j >= l + h && v < a[j - h])
            {
                a[j] = a[j - h]; j -= h;
            }
            a[j] = v;
        }
    }
}

My question under what basis author is checking for condition h <= (r-l)/9, and why author is dividing by 9.

is for (h = 1; h <= (r-l)/9; h = 3*h+1); just used to compute h for the next for loop? — NathanOliver
– NathanOliver, Commented May 4, 2015 at 12:15
Check the gap sequences on shell short en.wikipedia.org/wiki/Shellsort#Gap_sequences — Tasos Vogiatzoglou
– Tasos Vogiatzoglou, Commented May 4, 2015 at 12:23

Maarten Bamelis · Accepted Answer · 2015-05-04 13:00:13Z

1

The loop:

for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);

calculates the initial value of h. This value must be smaller than the range it will be used in:

h <= (r - l)

Everytime this condition passes, h gets updated to 3 * h + 1, which means that even though h is smaller than (r-l), the updated value might be larger. To prevent this, we could check if the next value of h would surpass the largest index:

(h * 3) + 1 <= (r - l)

This will make sure h is smaller than range of the array.

For example: say we have an array of size 42, which means indices go from 0 to 41. Using the condition as described above:

h = 1, is (3 * 1 + 1) <= (41 - 0) ? yes! -> update h to 4
h = 4, is (3 * 4 + 1) <= (41 - 0) ? yes! -> update h to 13
h = 13, is (3 * 13 + 1) <= (41 - 0) ? yes! -> update h to 40
h = 40, is (3 * 40 + 1) <= (41 - 0) ? no! => h will begin at 40

This means our initial h is 40, because h is only marginally smaller than the range of the array, very little work will be done, the algorithm will only check the following:

Does array[40] needs to be swapped with array[0] ?
Does array[41] needs to be swapped with array[1] ?

This is a bit useless, the first iteration only performs two checks. A smaller initial value of h means more work will get done in the first iteration.

Using:

h <= (r - l) / 9

ensures the initial value of h to be sufficiently small to allow the first iteration to do useful work. As an extra advantage, it also looks cleaner than the previous condition.

You could replace 9 by any value greater than 3. Why greater than 3? To ensure (h * 3) + 1 <= (r - l) is still true!

But do remember to not make the initial h too small: Shell Sort is based on Insertion Sort, which only performs well on small or nearly sorted arrays. Personally, I would not exceed h <= (r - l) / 15.

edited May 4, 2015 at 13:00

answered May 4, 2015 at 12:26

Maarten Bamelis

2,47323 silver badges39 bronze badges

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

2 Comments

venkysmarty Over a year ago

Thanks for explanation, it means we can select 10, or 11 to allow h value to be sufficiently small. Am I understanding is right. Other point you mentioned that h is 40 but 42-0 is 42 so how we got 40 here.

Maarten Bamelis Over a year ago

I have corrected and updated my answer with an example. You could very well select 10 or 11 to be used. Don't choose it too big, Insertion Sort (on which Shell Sort is based), only works well on small or nearly sorted arrays. Personally, I would take 15 as a maximum value.

Collectives™ on Stack Overflow

shell sort sequence implementation in C++

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related