Comb Sort

Comb sort is a relatively simplistic sorting algorithm originally designed by Wlodzimierz Dobosiewicz in 1980. Later it was rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine article published in April 1991. Comb sort improves on bubble sort, and rivals algorithms like Quicksort. The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. (Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.).

In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than one.

The gap starts out as the length of the list being sorted divided by the shrink factor (generally 1.3), and the list is sorted with that value (rounded down to an integer if needed) for the gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.

public IList CombSort(IList arrayToSort)
{
    int gap = arrayToSort.Count;
    int swaps = 0;

    do
    {
        gap = (int)(gap / 1.247330950103979);
        if (gap < 1)
        {
            gap = 1;
        }
        int i = 0;
        swaps = 0;

        do
        {
            if (((IComparable)arrayToSort[i]).CompareTo(arrayToSort[i + gap]) > 0)
            {
                object temp = arrayToSort[i];
                arrayToSort[i] = arrayToSort[i + gap];
                arrayToSort[i + gap] = temp;
                RedrawItem(i);
                RedrawItem(i + gap);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
                swaps = 1;
            }
            i++;
        } while (!(i + gap >= arrayToSort.Count));

    } while (!(gap == 1 && swaps == 0));

    return arrayToSort;
}