Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz in 1980. Later it was rediscovered by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble sort.

The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.

Complexity

  • Time: worst , best , average , where is the number of increment)
  • Space: worst auxiliary

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

    import org.algorithm_visualizer.*;

import java.util.Arrays;

class Main {

    private static ChartTracer chartTracer = new ChartTracer();

    private static LogTracer logTracer = new LogTracer("Console");

    private static Array1DTracer tracer = new Array1DTracer();

    private static Integer[] array = (Integer[]) new Randomize.Array1D(15, new Randomize.Integer(1, 20)).create();

    public static void main(String[] args) {
        tracer.set(array);
        tracer.chart(chartTracer);
        Layout.setRoot(new VerticalLayout(new Commander[]{chartTracer, tracer, logTracer}));
        logTracer.printf("original array = %s\n", Arrays.toString(array));

        Tracer.delay();

        int length = array.length;

        int gap = length;

        boolean swapped;

        float shrink = 1.3f;

        do {
            swapped = false;

            gap = (int) Math.floor(gap / shrink);

            if(gap < 1){
                gap = 1;
            }

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

        } while (gap != 1 || swapped);


        logTracer.printf("sorted array = %s\n", Arrays.toString(array));
    }

    private static void swap(int x, int y, Integer[] array) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
        tracer.patch(x, array[x]);
        tracer.patch(y, array[y]);
        Tracer.delay();
        tracer.depatch(x);
        tracer.depatch(y);
    }

}

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

    console.log(`original array = [${D.join(', ')}]`);

const N = D.length;
let swapped;
let gap = N; // initialize gap size
const shrink = 1.3; // set the gap shrink factor

do {
  // update the gap value for the next comb.
  gap = Math.floor(gap / shrink);
  if (gap < 1) {
    // minimum gap is 1
    gap = 1;
  }

  swapped = false; // initialize swapped
  // a single comb over the input list
  for (let i = 0; i + gap < N; i++) {

    if (D[i] > D[i + gap]) {
      
      console.log(`swap ${D[i]} and ${D[i + gap]}`); // log swap event

      const temp = D[i];
      D[i] = D[i + gap];
      D[i + gap] = temp;

      swapped = true; // Flag swapped has happened and list is not guaranteed sorted
    }
    
  } // End of combing
} while (gap !== 1 || swapped);