shell sort sequence implementation in C++

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.

Answers


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:

  1. Does array[40] needs to be swapped with array[0] ?
  2. 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.


Need Your Help

Search for specific value in Array

php arrays

I have an issue with an array being returned from an API request which i want to search for a specific value and perform a certain operation for but i have been unsucessful in making it work. I hav...

Enqueue, Dequeue and ViewQueue in Java

java queue

I am doing a queue in java. Here is my code: