# Java Comb Sort Algorithm Implementation

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]