Function comb_sort

Synopsis

#include <include/EASTL/sort.h>

template <typename ForwardIterator, typename StrictWeakOrdering>
void comb_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare)

Description

comb_sort

This is an unstable sort. Implements the CombSort algorithm; in particular, implements the CombSort11 variation of the CombSort algorithm, based on the reference to '11' in the implementation.

To consider: Use a comb sort table instead of the '((nSpace * 10) + 3) / 13' expression. Ideal tables can be found on the Internet by looking up "comb sort table".

Mentioned in

• FAQ / EASTL coverage of std STL

Source

Lines 1763-1792 in include/EASTL/sort.h.

template <typename ForwardIterator, typename StrictWeakOrdering>
void comb_sort(ForwardIterator first, ForwardIterator last, StrictWeakOrdering compare)
{
    typedef typename eastl::iterator_traits<ForwardIterator>::difference_type difference_type;
    ForwardIterator iCurrent, iNext;
    difference_type length = eastl::distance(first, last);
    difference_type nSpace = length;
    for(bool bSwapped = false; (nSpace > 1) || bSwapped; )
    {
        nSpace = ((nSpace * 10) + 3) / 13; // Integer division is less than ideal.
        if((nSpace == 9) || (nSpace == 10))
            nSpace = 11;
        iCurrent = iNext = first;
        eastl::advance(iNext, nSpace);

        for(bSwapped = false; iNext != last; iCurrent++, iNext++)
        {
            if(compare(*iNext, *iCurrent))
            {
                EASTL_VALIDATE_COMPARE(!compare(*iCurrent, *iNext)); // Validate that the compare function is sane.
                eastl::iter_swap(iCurrent, iNext);
                bSwapped = true;
            }
        }
    }
} // comb_sort

Synopsis

#include <include/EASTL/sort.h>

template <typename ForwardIterator>
void comb_sort(ForwardIterator first, ForwardIterator last)

Description

No description yet.

Mentioned in

• FAQ / EASTL coverage of std STL

Source

Lines 1794-1800 in include/EASTL/sort.h.

template <typename ForwardIterator>
inline void comb_sort(ForwardIterator first, ForwardIterator last)
{
    typedef eastl::less<typename eastl::iterator_traits<ForwardIterator>::value_type> Less;
    eastl::comb_sort<ForwardIterator, Less>(first, last, Less());
}