Comb Sort

Comb Sort is an improvement over Bubble Sort. It works by eliminating turtles, or small values near the end of the list, since in a bubble sort, these slow down the sorting process significantly. The basic idea is to compare elements with a certain gap between them, and then progressively reduce the gap while keeping the elements compared and swapped as necessary.


Algorithm:

Bubble Sort Visualization
Complexity
Best Time Complexity O(n log n)
Average Time Complexity O(n3/2)
Worst Time Complexity O(n2)
Space Complexity O(n)

Comb Sort Visualizer

Comb Sort Code

public void combSort(int[] arr) {
                        int gap = arr.length;
                        boolean swapped = true;
                        while (gap != 1 || swapped) {
                            gap = getNextGap(gap);
                            swapped = false;
                            for (int i = 0; i < arr.length - gap; i++) {
                                if (arr[i] > arr[i + gap]) {
                                    int temp = arr[i];
                                    arr[i] = arr[i + gap];
                                    arr[i + gap] = temp;
                                    swapped = true;
                                }
                            }
                        }
                    }
                    
                    int getNextGap(int gap) {
                        gap = (gap * 10) / 13;
                        if (gap < 1) return 1;
                        return gap;
                    }
void combSort(int arr[], int n) {
                        int gap = n;
                        bool swapped = true;
                        while (gap != 1 || swapped) {
                            gap = getNextGap(gap);
                            swapped = false;
                            for (int i = 0; i < n - gap; i++) {
                                if (arr[i] > arr[i + gap]) {
                                    int temp = arr[i];
                                    arr[i] = arr[i + gap];
                                    arr[i + gap] = temp;
                                    swapped = true;
                                }
                            }
                        }
                    }
                    
                    int getNextGap(int gap) {
                        gap = (gap * 10) / 13;
                        if (gap < 1) return 1;
                        return gap;
                    }
void combSort(vector<int>& arr) {
                        int gap = arr.size();
                        bool swapped = true;
                        while (gap != 1 || swapped) {
                            gap = getNextGap(gap);
                            swapped = false;
                            for (int i = 0; i < arr.size() - gap; i++) {
                                if (arr[i] > arr[i + gap]) {
                                    swap(arr[i], arr[i + gap]);
                                    swapped = true;
                                }
                            }
                        }
                    }
                    
                    int getNextGap(int gap) {
                        gap = (gap * 10) / 13;
                        if (gap < 1) return 1;
                        return gap;
                    }
def comb_sort(arr):
                        gap = len(arr)
                        swapped = True
                        while gap != 1 or swapped:
                            gap = get_next_gap(gap)
                            swapped = False
                            for i in range(len(arr) - gap):
                                if arr[i] > arr[i + gap]:
                                    arr[i], arr[i + gap] = arr[i + gap], arr[i]
                                    swapped = True
                    
                    def get_next_gap(gap):
                        gap = (gap * 10) // 13
                        return max(1, gap)

Practice Questions

Question Number Question Title Level Link
1 Sort an Array Easy Link
2 Sort List Medium Link
3 Merge k Sorted Lists Hard Link