Write a Java program to implement Comb Sort algorithm.

Java Comb Sort Algorithm Implementation

package net.sourcecodeexamples.java.Sorts;

import java.util.Arrays;


/**
 * Comb Sort algorithm implementation
 * <p>
 * Best-case performance O(n * log(n))
 * Worst-case performance O(n ^ 2)
 * Worst-case space complexity O(1)
 * <p>
 * Comb sort improves on bubble sort.
 * @see BubbleSort
 * @see SortAlgorithm
 */
class CombSort implements SortAlgorithm {

    // To find gap between elements
    private int nextGap(int gap) {
        // Shrink gap by Shrink factor
        gap = (gap * 10) / 13;
        return (gap < 1) ? 1 : gap;
    }

    /**
     * Function to sort arr[] using Comb
     *
     * @param arr - an array should be sorted
     * @return sorted array
     */
    @Override
    public < T extends Comparable < T >> T[] sort(T[] arr) {
        int size = arr.length;

        // initialize gap
        int gap = size;

        // Initialize swapped as true to make sure that loop runs
        boolean swapped = true;

        // Keep running while gap is more than 1 and last iteration caused a swap
        while (gap != 1 || swapped) {
            // Find next gap
            gap = nextGap(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 < size - gap; i++) {
                if (less(arr[i + gap], arr[i])) {
                    // Swap arr[i] and arr[i+gap]
                    swapped = swap(arr, i, i + gap);
                }
            }
        }
        return arr;
    }

    /**
     * Helper method for swapping places in array
     *
     * @param array The array which elements we want to swap
     * @param idx   index of the first element
     * @param idy   index of the second element
     */
    static < T > boolean swap(T[] array, int idx, int idy) {
        T swap = array[idx];
        array[idx] = array[idy];
        array[idy] = swap;
        return true;
    }


    /**
     * This method checks if first element is less than the other element
     *
     * @param v first element
     * @param w second element
     * @return true if the first element is less than the second element
     */
    static < T extends Comparable < T >> boolean less(T v, T w) {
        return v.compareTo(w) < 0;
    }

    // Driver method
    public static void main(String[] args) {
        CombSort ob = new CombSort();
        Integer[] arr = {
            0,
            36,
            34,
            8,
            12,
            -66,
            -78,
            23,
            -6,
            28,
            0
        };
        ob.sort(arr);

        System.out.println("sorted array");
        System.out.println(Arrays.toString(arr));
    }
}

Output

sorted array
[-78, -66, -6, 0, 0, 8, 12, 23, 28, 34, 36]