Comb Sort — VisualAlgorithms Docs

How it works

Improves on bubble sort by using a gap that shrinks by factor 1.3 each pass. Eliminates turtles (small values near end) much faster.

Implementation

      
 function combSort(arr) {
  let gap = arr.length, swapped = true;
  while (gap > 1 || swapped) {
    gap = Math.max(1, Math.floor(gap / 1.3));
    swapped = false;
    for (let i = 0; i + gap < arr.length; i++) {
      if (arr[i] > arr[i + gap]) {
        [arr[i], arr[i+gap]] = [arr[i+gap], arr[i]];
        swapped = true;
      }
    }
  }
} def comb_sort(arr):
    gap = len(arr)
    swapped = True
    while gap > 1 or swapped:
        gap = max(1, int(gap / 1.3))
        swapped = False
        for i in range(len(arr) - gap):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i+gap] = arr[i+gap], arr[i]
                swapped = True void combSort(vector<int>& arr) {
  int gap = arr.size();
  bool swapped = true;
  while (gap > 1 || swapped) {
    gap = max(1, (int)(gap / 1.3));
    swapped = false;
    for (int i = 0; i + gap < (int)arr.size(); i++)
      if (arr[i] > arr[i+gap]) {
        swap(arr[i], arr[i+gap]);
        swapped = true;
      }
  }
} void CombSort(int[] arr) {
  int gap = arr.Length;
  bool swapped = true;
  while (gap > 1 || swapped) {
    gap = Math.Max(1, (int)(gap / 1.3));
    swapped = false;
    for (int i = 0; i + gap < arr.Length; i++)
      if (arr[i] > arr[i+gap]) {
        (arr[i], arr[i+gap]) = (arr[i+gap], arr[i]);
        swapped = true;
      }
  }
} void combSort(int arr[], int n) {
  int gap = n, swapped = 1;
  while (gap > 1 || swapped) {
    gap = gap * 10 / 13;
    if (gap < 1) gap = 1;
    swapped = 0;
    for (int i = 0; i + gap < n; i++)
      if (arr[i] > arr[i+gap]) {
        int t = arr[i]; arr[i] = arr[i+gap]; arr[i+gap] = t;
        swapped = 1;
      }
  }
} 