Comb sort algorithm Java

Sorting algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data. There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements. To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and program them in Java. Today we are going to look at ridge sorting.

Comb sort algorithm

Ridge sorting is a sorting algorithm invented by Polish computer scientist Włodzimierz Dobosiewicz to improve sorting algorithms based on the element replacement method. If you read our article on Bubble Sort, you already know that its biggest drawback is that there are scenarios where sorting elements is not efficient for this algorithm. for example small elements that are at the end of the array are problematic in ascending sorting and large elements that are at the beginning of the array are problematic in descending sorting, because it takes quite a lot of iterations for a given element to be repositioned during sorting. Comb sort solves this by focusing on such problematic elements at the beginning of the sorting process and replacing them as a priority.

Comb sort definition explained

The basic idea of comb sort is that it quickly eliminates small values near the end of the list (called turtles), because in bubble sort it slows down sorting significantly by using a gap (or ridge) that gets progressively smaller. Large values around the beginning of the list, do not pose a problem in bubble/ridge sorting. When any two elements in a bubble sort are compared, they always have a gap (distance apart) of 1. The basic idea of ridge sorting is that the gap can be much larger than 1 and it doesn’t have to be a fixed constant at all and can change after iterations. The gap starts with a large value, usually the same as the length of the sorted field, and then decreases by some factor (usually around 1.3). This process is repeated until the gap reaches 1, at which point the algorithm behaves like normal bubble sort, but at this point the array is already partially ordered, making the final iteration more efficient. Experimentally, it has been found that too small a gap value slows down the algorithm by making unnecessarily many comparisons, while too large a gap value cannot deal with turtles efficiently, so it requires many transitions with a gap of 1.

Comb sort algorithm advantages:

• is easy to understand and implement,
• does not require additional memory for sorting,
• solves the problem of small values at the end of the list,
• on average is faster than Bubble sort.

Comb sort algorithm disadvantages – time complexity:

• However, the time complexity is still O(n²), which makes it a slow algorithm for a large dataset,
• is not stable.

Comb sort time requirement

Comb sort animation, visualization, gif

A visualisation of the Comb sort algorithm looks like this:

Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

You can find an animation of the Comb sort algorithm for example on this Page.

Comb Sort Implementation – Example in Java, data structure

Let’s program this algorithm with a dynamic gap in Java. CombSort.java

package sorting;

public class CombSort {
    private boolean change;
    private int temp;
    private int gap;

    public void sort(int data[])
    {
        change = false;
        // gap init
        gap = data.length;
        int i = 0;
        while (gap != 1 || change) {
            change = false;
            // calculate new gap
            gap /= 1.33;
            if(gap <= 1)
                gap = 1;
            System.out.println(++i + ". iteration (gap = " + gap + ")");
            for (int j = 0; j + gap < data.length; j++) {
                if (data[j] > data[j + gap]) {
                    temp = data[j];
                    data[j] = data[j + gap];
                    data[j + gap] = temp;
                    change = true;
                    printArray(data);
                }
            }
            // If no two elements swapped, then end the sort method
            if (!change)
                return;
        }
    }

    // Function to print an array
    public void printArray(int data[])
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

Main.java

import sorting.CombSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        CombSort combSort = new CombSort();
        System.out.print("Input: ");
        combSort.printArray(dataToSort);
        combSort.sort(dataToSort);
        System.out.print("Sorted: ");
        combSort.printArray(dataToSort);
    }
}

The output of this example is: We have prepared the above example files in the form of code that you can execute directly in Java. Download Comb Sort code in Java. If you’re a Java developer looking for a job, check out our employee benefits and respond to our job offers.

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.