(algorithm)
Definition: An in-place sort algorithm that repeatedly reorders different pairs of items. On each pass swap pairs of items separated by the increment or gap, if needed, and reduce the gap (divide it by about 1.3). The gap starts at about 3/4 of the number of items. Continue until the gap is 1 and a pass had no swaps.
Generalization (I am a kind of ...)
diminishing increment sort.
See also bubble sort, Shell sort.
Note: Bubble sort can be seen as a variant of comb sort where the gap is always 1. Since items may move large distances at first, comb sort is quite efficient.
Comb sort does a single "bubbling" pass (ala bubble sort) over each set for each gap or increment, whereas Shell sort completely sorts each set.
Author: PEB
Richard Box and Stephen Lacey, A fast, easy sort, Byte, 16(4):315-ff, April 1991.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 17 December 2007.
HTML page formatted Mon Dec 17 11:13:12 2007.
Cite this as:
Paul E. Black, "comb sort", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 17 December 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/combSort.html
