Comb Sort Algorithm
The Comb Sort Algorithm is an advanced sorting technique that builds upon the basic concepts of the Bubble Sort Algorithm. It is an efficient, in-place, comparison-based sorting algorithm, invented by Wlodzimierz Dobosiewicz and Artur Borowy in 1980, and later optimized by Stephen Lacey and Richard Box in 1991. The fundamental idea behind comb sort is to eliminate small values toward the end of the list and large values toward the beginning of the list, referred to as "turtles" and "rabbits" respectively, which cause the Bubble Sort algorithm to be slow. To achieve this, Comb Sort uses a variable gap between elements to be compared, which is gradually reduced to 1 as the algorithm progresses, ultimately becoming a simple Bubble Sort.
During the execution of the Comb Sort Algorithm, the list is traversed, and elements that are separated by the gap are compared and swapped if they are in the wrong order. The gap is initially set to a large value, typically the list length divided by a shrink factor (usually 1.3), and is reduced by the shrink factor in each iteration until it reaches 1. At this point, the algorithm turns into a conventional Bubble Sort, and the final step of the process is to iterate through the list, comparing and swapping adjacent elements as necessary. The Comb Sort algorithm is particularly effective for sorting lists that are partially ordered or have a small number of inversions, as it takes advantage of the existing order to quickly sort the data. While it is not as fast as more advanced algorithms like QuickSort or MergeSort, Comb Sort is an improvement over the basic Bubble Sort, offering better performance for large lists and partially ordered data.
package Sorts;
import static Sorts.SortUtils.*;
/**
* 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.
*
* @author Sandeep Roy (https://github.com/sandeeproy99)
* @author Podshivalov Nikita (https://github.com/nikitap492)
* @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;
}
// Driver method
public static void main(String[] args) {
CombSort ob = new CombSort();
Integer[] arr = {8, 4, 1, 56, 3, -44, -1, 0, 36, 34, 8, 12, -66, -78, 23, -6, 28, 0};
ob.sort(arr);
System.out.println("sorted array");
print(arr);
}
}
