Comb Sort is mainly an improvement over Bubble Sort. Bubble sort always compares adjacent values. So all inversions 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 Bubble Sort.
The shrink factor has been empirically found to be 1.3 (by testing Combsort on over 200, 000 random lists) [Source: Wiki]
Although, it works better than Bubble Sort on average, worst case remains O(n2).
Java
// Java program for implementation of Comb Sortimport java.io.*;public class CombSort { // 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 arr[] using Comb Sort void sort(int arr[]) { int n = arr.length; // initialize gap int gap = n; // 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 == 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 (arr[i] > arr[i + gap]) { // Swap arr[i] and arr[i+gap] int temp = arr[i]; arr[i] = arr[i + gap]; arr[i + gap] = temp; // Set swapped swapped = true; } } } } // Driver method public static void main(String args[]) { CombSort ob = new CombSort(); int arr[] = { 8, 4, 1, 56, 3, -44, 23, -6, 28, 0 }; ob.sort(arr); System.out.println("sorted array"); for (int i = 0; i < arr.length; ++i) System.out.print(arr[i] + " "); }}/* This code is contributed by Rajat Mishra */ |
sorted array -44 -6 0 1 3 4 8 23 28 56
Time Complexity: The worst-case complexity of this algorithm is O(n2).
Auxiliary Space: O(1).
Please refer complete article on Comb Sort for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
