Comb Sort - GeeksforGeeks

Comb Sort - GeeksforGeeks

Comb Sort is mainly an improvement over Bubble Sort. Bubble sort always compares adjacent values. So allinversions are removed one by one. Comb Sort improves on Bubble Sort by using gap of size more than 1. The gap starts with a large value and shrinks by a factor of 1.3 in every iteration until it reaches the value 1. Thus Comb Sort removes more than one inversion counts with one swap and performs better than Bublle Sort.

https://en.wikipedia.org/wiki/Comb_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.

In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1 (Shell sort is also based on this idea, but it is a modification of insertion sort rather than bubble sort).

In other words, the inner loop of bubble sort, which does the actual swap, is modified such that gap between swapped elements goes down (for each iteration of outer loop) in steps of shrink factor. i.e. [ input size / shrink factor, input size / shrink factor^2, input size / shrink factor^3, ...., 1 ]. Unlike in bubble sort, where the gap is constant i.e. 1.

// To find gap between elements

int getNextGap(int gap)

{

    // Shrink gap by Shrink factor

    gap = (gap*10)/13;

 

    if (gap < 1)

        return 1;

    return gap;

}

 

// Function to sort a[0..n-1] using Comb Sort

void combSort(int a[], int n)

{

    // Initialize gap

    int gap = n;

 

    // Initialize swapped as true to make sure that

    // loop runs

    int swapped = true;

 

    // Keep running while gap is more than 1 and last

    // iteration caused a swap

    while (gap != 1 || swapped == true)

    {

        // Find next gap

        gap = getNextGap(gap);

 

        // Initialize swapped as false so that we can

        // check if swap happened or not

        swapped = false;

 

        // Compare all elements with current gap

        for (int i=0; i<n-gap; i++)

        {

            if (a[i] > a[i+gap])

            {

                swap(a[i], a[i+gap]);

                swapped = true;

            }

        }

    }

}

Read full article from Comb Sort - GeeksforGeeks