Kev

I just made some tweaks to the combsort. Basically, my version will now sort over a range of the array. You give it a start index, and then you give it how many integers from that index (including that index) you want to sort. The new code looks something like this:

void combsort_ranged(int * input, unsigned start, unsigned len, int (*comparison)(int *s0, int *s1))
{
    unsigned end = start + len;
    unsigned gap = len;
    unsigned int swaps = 0xFFFF;

    while(gap > 1 || swaps != 0)
    {
        if (gap > 1)
        {
            gap /= 1.3;
            if (gap == 10 || gap == 9)
                gap = 11;
        }

        unsigned i = start;
        swaps = 0;

        while (i + gap < end)
        {
            if (comparison(&(input[i]), &(input[i + gap])) > 0)
            {
                // Swap input[i] and input[i + gap]
                int temp = input[i];
                input[i] = input[i + gap];
                input[i + gap] = temp;
                swaps = 1;
            }

            i++;
        }
    }
}

As I was working today on an MP, I needed a sorting algorithm that would work well with linked lists. For those of you who have ever written a linked list data structure of some kind, you will know that splitting and reallocated buffers and such is a pain. Sorting algorithms such as mergesort, heapsort, and quicksort use those kinds of techniques, making them very hard to implement on a linked list.

“But…”, you say, “mergesort and heapsort and quicksort all give us really good running times and memory usage!” Well my friends, do not fear, for there is another sorting algorithm I had never heard of until today: combsort. The idea of combsort is similar to that of bubblesort: going through the buffer linearly as many times as need, and the running comparisons on particular elements. No reallocation is done, no splitting, just the exchange of elements.

Yet again, bubblesort falls very short of the O(nlogn) running time of quick/merge/heapsort. But amazingly enough, combsort also runs in O(nlogn) as well! This makes combsort an extremely attractive option for a number of reasons:

• O(nlogn) average and worst case running time which is right up there with merge/heap/quicksort.
• O(1) memory usage.
• Small code size.

Here is the C code for running combsort:

void combsort(int * input, unsigned count, int (*comparison)(int *s0, int *s1))
{
    unsigned gap = count;
    unsigned int swaps = 0xFFFF;

    while(gap > 1 || swaps != 0)
    {
        if (gap > 1)
        {
            gap /= 1.3; // Funky magic number
            if (gap == 10 || gap == 9)
                gap = 11;
        }

        unsigned i = 0;
        swaps = 0;

        while (i + gap < count)
        {
            if (comparison(&(input[i]), &(input[i + gap])) > 0)
            {
                // Swap input[i] and input[i + gap]
                int temp = input[i];
                input[i] = input[i + gap];
                input[i + gap] = temp;
                swaps = 1;
            }

            i++;
        }
    }
}

How does Combsort perform?:
When sorting the same buffer of 10,000,000 integers, I got the following average times for different sorting algorithms.

BubbleSort  > 24300.000 s  // Or about 6.75 hours.
HeapSort         14.518 s
CombSort         11.189 s
MergeSort         5.789 s
QuickSort         4.497 s

So as you can see, combsort performs pretty dang well.

Conclusion:
Basically, I love combsort and I intend on making it my choice sorting algorithm for linked list structures, or any other structures where I don’t want to have to allocate some memory. To read more about combsort, check out its Wikipedia page.