combsort implementation. review.

[monarch_dodra]

Hi,

i was over at wikipedia reading about combsort (http://en.wikipedia.org/wiki/Comb_sort), I I fell on this c++ implementation.

template<class t> inline void combsort(t*a, int n)
{
  int g=n,s=2;
  t*j,*i,z;
  while(s>1)for(i=a-1,s=g=(g/=1.3)>8&g<11?11:g?:1;++i<a+n-g;)z=*i,z>*(j=i+g)?s++,*i=*j,*j=z:7;
}

While I am sure writing this kind of code is fun, I am pretty sure reading about it won't help anyone. Also, I am pretty sure this function shouldn't be inline.

I would like to re-write this pseudo algorithm:

function combsort11(array input)
    gap := input.size //initialize gap size
    
    loop until gap <= 1 and swaps = 0
        //update the gap value for a next comb
        if gap > 1
            gap := gap / 1.3
            if gap = 10 or gap = 9
                gap := 11
            end if
        end if
        
        i := 0
        swaps := 0 //see bubblesort for an explanation
        
        //a single "comb" over the input list
        loop until i + gap >= input.size //see shellsort for similar idea
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                swaps := 1 // Flag a swap has occurred, so the list is not guaranteed sorted
            end if
            i := i + 1
        end loop
       
    end loop
end function

And I wrote this. I wanted the algorithm to be stl-style, easy to understand, and scalable. Could you guys look at it and tell me what you think? if somethings need change before I submit it?

template<class ForwardIterator>
void combsort ( ForwardIterator first, ForwardIterator last )
{
    static const double shrink_factor = 1.247330950103979;
    typename ForwardIterator::difference_type gap = std::distance(first, last);
    bool swaps = true;

    while ( (gap > 1) || (swaps == true) )
    {
        if (gap > 1)
        {
            gap = static_cast<typename ForwardIterator::difference_type>(
                gap/shrink_factor
            );
            if ( (gap == 10) || (gap == 9) ) {gap = 11;}
        }
        swaps = false;
        ForwardIterator itLeft(first);
        ForwardIterator itRight(first); std::advance(itRight, gap);
        
        for ( ; itRight!=last; ++itLeft, ++itRight )
        {
            if ( (*itRight) < (*itLeft) )
            {
                std::iter_swap(itLeft, itRight);
                swaps = true;
            }
        }
    }
}

[ltcmelo]

Hello again.

One problem I could note right way is that you assume a typedef for the iterator type. Remember from our recente discussion?

Well, that's the whole point of std::iterator_traits. Some iterators classes do provide typedefs like difference_type. Others don't and need to specialize std::iterator_traits. A good example is a pointer. Pointers are built-ins and can't have a typedef inside. So there's an specialization of std::iterator_traits for pointers. (Try to compile your code passing a pointer to the function and you'll see the error.)

The rule is that whenever you need to mention difference_type (or its related typedefs) you should use std::iterator_traits.

typename std::iterator_traits<ForwardIterator>::difference_type gap = std::distance(first, last);

You also assume some requirements on the value_type of the iterator (the type that the iterator points to). For instance, you expect that they support operator <. If you don't want to depend on that you should use a function object as an additional template parameter. If you do, it would be good just to make it clear on the documentation.

This is a first impression...

[monarch_dodra]

Originally Posted by ltcmelo

Hello again.

One problem I could note right way is that you assume a typedef for the iterator type. Remember from our recente discussion?

Well, that's the whole point of std::iterator_traits. Some iterators classes do provide typedefs like difference_type. Others don't and need to specialize std::iterator_traits. A good example is a pointer. Pointers are built-ins and can't have a typedef inside. So there's an specialization of std::iterator_traits for pointers. (Try to compile your code passing a pointer to the function and you'll see the error.)

The rule is that whenever you need to mention difference_type (or its related typedefs) you should use std::iterator_traits.

typename std::iterator_traits<ForwardIterator>::difference_type gap = std::distance(first, last);

You also assume some requirements on the value_type of the iterator (the type that the iterator points to). For instance, you expect that they support operator <. If you don't want to depend on that you should use a function object as an additional template parameter. If you do, it would be good just to make it clear on the documentation.

This is a first impression...

Thankyou for the details about iterator_traits. I guess it is still not 100% clear. However, this finally clears up why you can't inherit from iterator traits

As for the operator<, then yes, I do make this assumption, like all std algorithms do. There is always a "simple" algorithm, and another one that takes a functor:

template <class RandomAccessIterator>
  void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

I could write the other implementation, but that would be overkill for wikipedia.

Thankyou. here is the new code that works with pointers.

template<class ForwardIterator>
void combsort ( ForwardIterator first, ForwardIterator last )
{
    static const double shrink_factor = 1.247330950103979;
    typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
    difference_type gap = std::distance(first, last);
    bool swaps = true;

    while ( (gap > 1) || (swaps == true) )
    {
        if (gap > 1)
        {
            gap = static_cast<difference_type>(
                gap/shrink_factor
            );
            if ( (gap == 10) || (gap == 9) ) {gap = 11;}
        }
        swaps = false;
        ForwardIterator itLeft(first);
        ForwardIterator itRight(first); std::advance(itRight, gap);
        
        for ( ; itRight!=last; ++itLeft, ++itRight )
        {
            if ( (*itRight) < (*itLeft) )
            {
                std::iter_swap(itLeft, itRight);
                swaps = true;
            }
        }
    }
}