Comb sort improves on bubble sort by comparing and swapping elements that are far apart rather than only adjacent elements, using a gap that starts large, typically the array length divided by a shrink factor of about 1.3, and shrinks on each pass down to a gap of one, at which point it behaves like an ordinary bubble sort pass on data that is by then mostly sorted. The larger initial gaps let small values near the end of the array move toward the front quickly instead of one step at a time. Wlodzimierz Dobosiewicz first described the underlying idea in 1980, and Stephen Lacey and Richard Box popularized it under the name comb sort in a 1991 Byte magazine article.
Facts
Time Complexity Credited ToDobosiewicz and Artur Borowy (1980); rediscovered and named by Stephen Lacey and Richard Box (1991) 1 Time Complexity
Time Complexity (category)Quadratic Time -- O(n^2) 1 Connections
In Field
Source Wikipedia: Comb sort
Sources
1. Wikipedia: Comb sort
Infobox, time
O(n^2)
Lead section
Dobosiewicz and Artur Borowy in 1980, later rediscovered (and given the name "Combsort") by Stephen Lacey and Richard Box in 1991
In Field: Algorithms and Complexity Theory, Lead sentence
Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered (and given the name "Combsort") by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort in the sa
In Group: Comparison Sorting Algorithms, Lead
Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered (and given the name "Combsort") by Stephen Lacey and Richard Box in 1991.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.