the shellsort algorithm

[johnmerlino]

Below is an implementation of the shellsort algorithm I got from the book:

void shellsort(int v[], int n)

{

    int gap, i, j, temp;



    for (gap = n/2; gap > 0; gap /= 2)

        for (i = gap; i < n; i++)

            for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {

                temp = v[j];

                v[j] = v[j+gap];

                v[j+gap] = temp;

            }

}

In our shellsort function, we define gap to be half of what n is. So if n is 10, then our gap will be 5. With a gap of 5, we will be swapping elements a distance of 5 indexes apart from each other. We assign gap to i and set i less than 10. Why we do this? Because i (5) less than 10 ensures we swap 50 percent of the number of elements total. Since we are swapping two elements, 50 * 2 = 100 and we will ultimately swap all elements. The i increment in the second-level for loop is critical. This ensures while our gap remains the same, we are working with different elements for each iteration. For example, first we work on elements 0 and 5, then 1 and 6, then 2 and 7, etc. How does this work? “i = gap” assins 5 to i in first run. j = i – gap is 0 in first run. So gap is 5 and j is 0, which is a gap of 5. Note the swap only occurs if v[j]>v[j+gap], that is, if the eleemnt in index 0 of v is GREATER THAN the element in index 5 of v.

Note the following: j-=gap. Since gap is always 5 and j increments from 0,1,2,3,4... that means the first 5 times this inner for loop runs, it will return a negative value to j (e.g. 0-5=-5), and thus since j will not be greater than or equal to 0, it will only run once. That's exactly what we want. We don't want to swap more than once, because if we did, we would only be swapping the same two values over again, thus causing unnecessary redundancy.

When i increments, then our gap shifts. For example, when i increments to 6, j will be 1, and j+gap will be 6. And if the value at 1 position in v is greater than the value in 5 position of v, then we swap them. And as i continues to increment, we have the potential to swap elements that are equal distance apart at different locations in the array.

The only question I have about this program is why in the first-level for loop is gap divided by 2: "gap /= 2". I don't understand the purpose of this.

[JLBorges]

> why in the first-level for loop is gap divided by 2: "gap /= 2".
> I don't understand the purpose of this.

In a shell sort, we have to choose the gap sequence.
The code snippet in the book opts for the original gap sequence used by Donald Shell (N/2, N/4, N/8 ...).

See 'How to choose gap size' in http://www.stoimen.com/blog/2012/02/27/computer-algorithms-shell-sort/

[johnmerlino]

I would like to make another point. What's interesting about this algorithm is the following: when gap is 5, we only swap elements once, we do no comparisons with the elements that have been demoted to lower positions (by comparing them with indexes 5 less than theirs). However, when the gap is 2, we have the potential of swapping elements multiple times. That is, if element at position 6 is demoted to position 4, then we compare that element at 4 to the element at position 2 and so forth. Why is it when gap is 2 we do this recursive search, but when gap is at position 5 we do not?

[JLBorges]

> when gap is 5, we only swap elements once,
> we do no comparisons with the elements that have been demoted to lower positions
> However, when the gap is 2, we have the potential of swapping elements multiple times
> Why is it when gap is 2 we do this recursive search, but when gap is at position 5 we do not?

No, the compare-swap logic would be the same for all gaps.

If we take the code that you originally posted with the gap sequence { N/2, N/4, N/8, ... 1 }
and modify it to take a different gap sequence which contains both 5 and 2 { 13, 9, 5, 2, 1 }
we can see that there is no special treatment for either 5 or for 2.

#include <iostream>
#include <algorithm>

void shell_sort( int array[], int n )
{
    static constexpr int gap_sequence[] = { 13, 9, 5, 2, 1 } ;

    // for (gap = n/2; gap > 0; gap /= 2)
    for( int gap : gap_sequence ) if( gap < n )
    {
        // for (i = gap; i < n; i++)
        for( int i = gap ; i < n; ++i )

            // for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap)
            for ( int j = i-gap ; j >= 0 && array[j] > array[j+gap] ; j -= gap )
                /*
                    temp = v[j];
                    v[j] = v[j+gap];
                    v[j+gap] = temp;
                */
                std::swap( array[j], array[j+gap] ) ;
    }
}

void print( const int array[], int n )
{
    for( int i = 0 ; i < n ; ++i ) std::cout << array[i] << ' ' ;
    std::cout << '\n' ;
}

int main()
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
    constexpr int N = sizeof(a) / sizeof( a[0] ) ;

    std::random_shuffle( a, a+N ) ;
    print( a, N ) ;
    shell_sort( a, N ) ;
    print( a, N ) ;
}

http://coliru.stacked-crooked.com/a/f8074ef2bff946a5