Comb sort

Comb sort
Visualisation of comb sort
Class Sorting algorithm
Data structure Array
Worst case performance O(n log n)[1]
Best case performance O(n log n)
Average case performance O(n log n)
Worst case space complexity O(n)

Comb sort is a relatively simplistic sorting algorithm originally designed by Włodzimierz 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 (visual comparison). 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. (Shell sort is also based on this idea, but it is a modification of insertion sort rather than bubble sort.)

The gap starts out as the length of the list being sorted divided by the shrink factor (generally 1.3; see below), 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.

Contents

Shrink factor

The shrink factor has a great effect on the efficiency of comb sort. In the original article, the authors suggested 1.3 after trying some random lists and finding it to be generally the most effective. A value too small slows the algorithm down because more comparisons must be made, whereas a value too large means that no comparisons will be made. Text[citation needed] describes an improvement to comb sort using the base value 1/\left(1-\frac{1}{e^\varphi}\right) \approx 1.247330950103979 as the shrink factor. It also contains a pseudocode implementation with a pre-defined gap table.

Variations

Combsort11

With a shrink factor around 1.3, there are only three possible ways for the list of gaps to end: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), or (11, 8, 6, 4, 3, 2, 1). Experiment shows that significant speed improvements can be made if the gap is set to 11 whenever it would otherwise become 9 or 10. This variation is called Combsort11.

If either of the sequences beginning with 9 or 10 were used, the final pass with a gap of 1 is less likely to completely sort the data, necessitating another pass with a gap of 1. The data is sorted when no swaps were done during a pass with gap = 1.

It is also possible to use a predefined table, to choose which gaps to use every pass.

Combsort with different end

Like many other sort efficient algorithms (like quick sort or merge sort), combsort is more effective in its earlier passes than it is during the final passes, when it resembles a bubble sort. Combsort can be made more effective if the sorting method is changed once the gaps reach numbers small enough. For example, once the gap reaches a size of about 10 or smaller, stopping the combsort and doing a simple gnome sort or cocktail sort, or, even better, an insertion sort, will increase the sort's overall efficiency.[citation needed]

Another advantage of this method is that there is no need to keep track of swaps during the sort passes to know if the sort should stop or not.

Examples

Pseudocode

function combsort(array input)
    gap := input.size //initialize gap size

    loop until gap = 1 and swaps = 0
        //update the gap value for a next comb. Below is an example
        gap := int(gap / 1.247330950103979)
        if gap < 1
          //minimum gap is 1
          gap := 1
        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

C99

void comb_sort(int *input, size_t size) {
    size_t gap = size;
    bool swapped = true;
 
    while ((gap > 1) || swapped) {
        if (gap > 1) {
            gap = (size_t)((double)gap / 1.247330950103979);
        }
 
        swapped = false;
 
        for (size_t i = 0; gap + i < size; i++) {
            if (input[i] - input[i + gap] > 0) {
                int swap = input[i];
                input[i] = input[i + gap];
                input[i + gap] = swap;
                swapped = true;
            }
        }
    }
}

References

  1. ^ V. Garcia; F. Nielsen (May 4-6, 2009). "Searching High-Dimensional Neighbours: CPU-Based Tailored Data-Structures Versus GPU-Based Brute-Force Method". Computer Vision/Computer Graphics Collaboration Techniques: 4th International Conference, MIRAGE 2009. Springer. pp. 425–436. 

See also

  • Bubble sort, a generally slower algorithm, is the basis of comb sort.
  • Cocktail sort, or bidirectional bubble sort, is a variation of bubble sort that also addresses the problem of turtles, albeit less effectively.

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Comb sort — En ciencias de la computación, el comb sort es un algoritmo de ordenamiento relativamente simple diseñado por Wlodzimierz Dobosiewicz en 1980. Posteriormente fue redescubierto y popularizado por Stephen Lacey y Richard Box en un artículo… …   Wikipedia Español

  • comb — [v1] arrange hair adjust, card, cleanse, curry, disentangle, dress, groom, hackle, hatchel, lay smooth, rasp, scrape, separate, smooth, sort, straighten, tease, untangle; concept 162 comb [v2] search by ransacking beat, beat the bushes*, examine …   New thesaurus

  • sort — [n] type, variety array, batch, battery, body, brand, breed, category, character, class, clutch, denomination, description, family, genus, group, ilk, kind, likes, likes of*, lot, make, nature, number, order, parcel, quality, race, set, species,… …   New thesaurus

  • comb — n 1. fine tooth comb, serration, serrated edge, toothed strip; hair comb, hairbrush, brush, currycomb; card; rake, harrow. 2. cock s comb, crest, tuft, Zool. caruncle, topknot; growth, Zool. beard, outgrowth, ridge, spine; feather, plume, panache …   A Note on the Style of the synonym finder

  • comb pottery — also called  combware        main pottery type of the Korean Neolithic Period (c. 3000–700 BC). Derived from a Siberian Neolithic prototype, the pottery is made of sandy clay, and its colour is predominantly brown. The vessel form found in early… …   Universalium

  • sort — Synonyms and related words: adjust, ailing, alphabetize, analyze, appraise, arrange, array, assess, assort, batch, battery, blood, body, body build, bolt, brand, break down, breed, bulk, cast, catalog, catalogue, categorize, category, character,… …   Moby Thesaurus

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

  • Bubble sort — Infobox Algorithm class=Sorting algorithm data=Array time= О(n²) space= О(n) total, O(1) auxiliary optimal=NoBubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.