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.

 

More posts tagged Sorting