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, stats) {
  const n = arr.length;
  let gap = n, shrink = 1.3, done = false;
  while (!done) {
    gap = Math.floor(gap / shrink);
    if (gap <= 1) {
      gap = 1;
      done = true;
    }
    for (let i = 0; i + gap < n; i++) {
      compare(i, i + gap);
      if (arr[i] > arr[i + gap]) {
        [arr[i], arr[i + gap]] = [arr[i + gap], arr[i]];
        swap(i, i + gap);
        done = false;
      }
    }
  }
  for (let i = 0; i < n; i++) markSorted(i);
}
 def combSort(arr, stats):
    gap = n
    shrink = 1.3
    done = False
    while not done:
        gap = int(gap / shrink)
        if (gap <= 1):
            gap = 1
            done = True
        i = 0
        while ((i + gap) < n):
            compare(i, (i + gap))
            if (arr[i] > arr[(i + gap)]):
                arr[i], arr[(i + gap)] = arr[(i + gap)], arr[i]
                swap(i, (i + gap))
                done = False
            i += 1
    for i in range(n):
        markSorted(i)
 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int gap = n;
    int shrink = 1.3;
    int done = 0;
    while(!done) {
        gap = (gap / shrink);
        if((gap <= 1)) {
            gap = 1;
            done = 1;
        }
        for(int i=0; ((i + gap) < n); i++) {
            compare(i, (i + gap));
            if((arr[i] > arr[(i + gap)])) {
                std::swap(arr[i], arr[(i + gap)]);
                swap(i, (i + gap));
                done = 0;
            }
        }
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} public void Sort(int[] arr, int n, dynamic stats) {
    int gap = n;
    int shrink = 1.3;
    int done = false;
    while(!done) {
        gap = (gap / shrink);
        if((gap <= 1)) {
            gap = 1;
            done = true;
        }
        for(int i=0; ((i + gap) < n); i++) {
            compare(i, (i + gap));
            if((arr[i] > arr[(i + gap)])) {
                { int _t = arr[i]; arr[i] = arr[(i + gap)]; arr[(i + gap)] = _t; }
                swap(i, (i + gap));
                done = false;
            }
        }
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} #include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    int gap = n;
    int shrink = 1.3;
    int done = 0;
    while(!done) {
        gap = (gap / shrink);
        if((gap <= 1)) {
            gap = 1;
            done = 1;
        }
        for(int i=0; ((i + gap) < n); i++) {
            compare(i, (i + gap));
            if((arr[i] > arr[(i + gap)])) {
                { int _t = arr[i]; arr[i] = arr[(i + gap)]; arr[(i + gap)] = _t; }
                swap(i, (i + gap));
                done = 0;
            }
        }
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} 