 # Comb sort

Published
Tags:

Comb sort is an O(n^2) variation of the bubble sort sorting algorithm.

Comb sort is similar to bubble sort in that is iterates through the list multiple times, swapping elements that are out of order as it goes. The difference is that comb sort doesn’t start off looking at adjacent elements but instead looks at elements a certain number of indexes apart, this is called the gap. The gap is defined as \lfloor n/c \rfloor, where n is the number of elements and c is the shrink factor which is typically set as 1.3. After each iteration, this number is against divided by c and floored until eventually the algorithm is looking at adjacent elements.

Similar to cocktail sort, comb sort improves upon bubble sort due to its ability to deal with the “turtles problem”. It does this by swapping elements that are separated by many indexes by a while the gap is large and progressively shifts them closer to their correct index as the algorithm continues.

## Complexity

Time Space
Worst case Best case Worst case
O(n^2) Θ(n \log n)* O(1) auxiliary

* I could not find a reliable source for this

## Visualisation

Use the controls to playback comb sort on the data set.

See the Sorting Visualiser page for more visualisations.

## Code

public class CombSort<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
public void Sort(IList<T> list)
{
int gap = list.Count;
float shrinkFactor = 1.3f;
bool swapped = false;

while (gap > 1 || swapped) {
if (gap > 1) {
gap = (int)(gap / shrinkFactor);
}

swapped = false;

for (int i = 0; gap + i < list.Count; i++) {
if (list[i].CompareTo(list[i + gap]) > 0) {
Swap(list, i, i + gap);
swapped = true;
}
}
}
}

private void Swap(IList<T> list, int a, int b)
{
T temp = list[a];
list[a] = list[b];
list[b] = temp;
}
}
public class CombSort {
public static void sort(Integer[] array) {
int gap = array.length;
float shrinkFactor = 1.3f;
boolean swapped = false;

while (gap > 1 || swapped) {
if (gap > 1) {
gap = (int)(gap / shrinkFactor);
}

swapped = false;

for (int i = 0; gap + i < array.length; i++) {
if (array[i] > array[i + gap]) {
swap(array, i, i + gap);
swapped = true;
}
}
}
}

private static void swap(Integer[] array, int a, int b) {
Integer temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
/**
* Sorts an array using comb sort.
* @param {Array} array The array to sort.
* @param {function} compare The compare function.
* @param {function} swap A function to call when the swap operation is
* performed. This can be used to listen in on internals of the algorithm.
* @returns The sorted array.
*/
function sort(array, compare, swap) {
var gap = array.length;
var shrinkFactor = 1.3;
var swapped;

while (gap > 1 || swapped) {
if (gap > 1) {
gap = Math.floor(gap / shrinkFactor);
}

swapped = false;

for (var i = 0; gap + i < array.length; ++i) {
if (compare(array, i, i + gap) > 0) {
swap(array, i, i + gap);
swapped = true;
}
}
}

return array;
}
def default_compare(a, b):
if a < b:
return -1
elif a > b:
return 1
return 0

def sort(array, compare=default_compare):
gap = len(array)
shrinkFactor = 1.3
swapped = False

while gap > 1 or swapped:
if gap > 1:
gap = math.floor(gap / shrinkFactor)
swapped = False
for i in range(len(array) - gap):
if compare(array[i], array[i + gap]) > 0:
array[i], array[i + gap] = array[i + gap], array[i]
swapped = True

return array
module CombSort
# Sorts an array using comb sort.
def self.sort(array, compare = lambda { |a, b| a <=> b })
gap = array.length
shrink_factor = 1.3
swapped = false
while gap > 1 || swapped
if gap > 1
gap = (gap / shrink_factor).floor
end
swapped = false
i = 0
while gap + i < array.length
if compare.call(array[i], array[i + gap]) > 0
array[i], array[i + gap] = array[i + gap], array[i]
swapped = true
end
i += 1
end
end
end
end

## Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.