# What is Comb Sort

**The Comb Sort**algorithm works by repeatedly swapping adjacent elements that are out of order, but it uses a more sophisticated technique for determining the spacing between the elements being compared. Instead of always comparing adjacent elements, as in Bubble Sort, Comb Sort starts by comparing elements that are far apart, and then gradually reduces the gap between them as the algorithm proceeds.

The gap between elements is determined by a "shrink factor" that is applied to the gap after each iteration. The shrink factor is usually chosen to be a value between 1.3 and 1.5, which has been found to provide good performance in practice.

The algorithm continues to swap adjacent elements and reduce the gap between them until the gap reaches a minimum value of 1, at which point the algorithm falls back to Bubble Sort to finish the sorting process

Simpler terms:

Imagine you have a bunch of cards with numbers on them, and you want to sort them in ascending order. One way to do this is to compare adjacent pairs of cards and swap them if they are in the wrong order. This is similar to how Bubble Sort works.

However, with Comb Sort, we use a different approach to decide which pairs of cards to compare. Instead of comparing adjacent pairs of cards, we start by comparing pairs of cards that are far apart from each other, like the first and tenth card. This helps to move larger cards to the end of the list faster.

After each comparison, we move the gap between the pairs of cards closer together by a "shrink factor," which is usually around 1.3 to 1.5. We keep doing this until the gap is 1, and at that point, we switch to Bubble Sort to finish sorting the list.

The key idea behind Comb Sort is that it tries to avoid having to make too many comparisons between adjacent pairs of cards by using a more efficient comparison strategy. This can make it faster than Bubble Sort for certain types of input data.

## Who invented it?

**was invented by Włodzimierz Dobosiewicz, a Polish computer scientist, in 1980. Dobosiewicz came up with the idea of using the shrink factor to determine the gap between elements being compared, which is a key feature of the algorithm. Comb Sort was initially developed as a variation of the Shell Sort algorithm, which also uses the concept of reducing the gap between elements being compared. However, Comb Sort is simpler to implement than Shell Sort and has been found to perform well in practice.**

The Comb Sort algorithm

The Comb Sort algorithm

## Pseudocode

```
function combSort(array)
gap = array.length
shrink = 1.3
swapped = true
while gap > 1 or swapped do
gap = floor(gap / shrink)
swapped = false
i = 0
while i + gap < array.length do
if array[i] > array[i + gap] then
swap(array[i], array[i + gap])
swapped = true
end if
i = i + 1
end while
end while
return array
end function
```

In this pseudocode implementation, array is the input array to be sorted. The algorithm starts with a gap value that is equal to the length of the array and a shrink factor of 1.3. It then enters a loop that repeats until the gap value is 1 and no swaps have been made during the previous iteration.

Inside the loop, the gap value is reduced by the shrink factor, and a flag is set to false indicating that no swaps have been made yet. The algorithm then iterates through the array, comparing each element with the one gap positions ahead of it. If the elements are out of order, they are swapped, and the flag is set to true.

Once the inner loop completes, the algorithm returns the sorted array.

Note that the swap function used in this pseudocode implementation is a simple function that swaps two elements in an array.

Inside the loop, the gap value is reduced by the shrink factor, and a flag is set to false indicating that no swaps have been made yet. The algorithm then iterates through the array, comparing each element with the one gap positions ahead of it. If the elements are out of order, they are swapped, and the flag is set to true.

Once the inner loop completes, the algorithm returns the sorted array.

Note that the swap function used in this pseudocode implementation is a simple function that swaps two elements in an array.

## Sample Code

```
// C++ code snippet
void combSort(vector
```& array) {
int gap = array.size();
double shrink = 1.3;
bool swapped = true;
while (gap > 1 || swapped) {
gap = floor(gap / shrink);
swapped = false;
int i = 0;
while (i + gap < array.size()) {
if (array[i] > array[i + gap]) {
swap(array[i], array[i + gap]);
swapped = true;
}
i++;
}
}
}
int main() {
vector array = {5, 2, 9, 1, 5, 6, 3};
combSort(array);
for (int i = 0; i < array.size(); i++) {
cout << array[i] << " ";
}
return 0;
}

```
# Python code snippet
import math
def comb_sort(arr):
gap = len(arr)
shrink = 1.3
swapped = True
while gap > 1 or swapped:
gap = math.floor(gap / shrink)
swapped = False
i = 0
while i + gap < len(arr):
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap] = arr[i + gap], arr[i]
swapped = True
i += 1
return arr
# Example usage:
arr = [5, 2, 9, 1, 5, 6, 3]
sorted_arr = comb_sort(arr)
print(sorted_arr)
```

```
import java.util.Arrays;
public class CombSort {
public static void combSort(int[] arr) {
int gap = arr.length;
double shrink = 1.3;
boolean swapped = true;
while (gap > 1 || swapped) {
gap = (int) Math.floor(gap / shrink);
swapped = false;
int i = 0;
while (i + gap < arr.length) {
if (arr[i] > arr[i + gap]) {
int temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
swapped = true;
}
i++;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6, 3};
combSort(arr);
System.out.println(Arrays.toString(arr));
}
}
```

## Time and Space Complexity

- The time complexity of Comb Sort is O(n^2) in the worst case, where n is the number of elements in the input array. However, in practice, Comb Sort often runs faster than other O(n^2) sorting algorithms due to its ability to "comb" out small values and avoid unnecessary swaps. The time complexity can be improved to O(n log n) by using a shrinking factor of 1.25 instead of 1.3, but this is still slower than most O(n log n) sorting algorithms.
- The space complexity of Comb Sort is O(1) since the algorithm sorts the input array in place and does not require any additional memory proportional to the size of the input. This makes Comb Sort a space-efficient sorting algorithm.

## Advantages

- Comb Sort is a simple and easy-to-implement sorting algorithm.
- It is a variation of Bubble Sort, but with better average-case performance and lower worst-case time complexity.
- The algorithm can be easily adapted to work on linked lists or other data structures with sequential access.
- Comb Sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the input array.
- The algorithm can be tuned for different types of input data by adjusting the shrink factor and/or choosing the optimal initial gap value.

## Disadvantages

- Although Comb Sort has a lower worst-case time complexity than Bubble Sort, it is still an O(n^2) sorting algorithm. This means that it can be slow for large input sizes and is not as efficient as O(n log n) sorting algorithms such as Merge Sort or Quick Sort.
- The performance of Comb Sort can be highly dependent on the choice of the shrink factor and the initial gap value. Choosing suboptimal values can lead to poor performance.
- Unlike some other sorting algorithms, such as Insertion Sort or Selection Sort, Comb Sort does not have any early termination mechanism to detect when the input array is already sorted. This means that it may perform unnecessary iterations and comparisons even when the input is already sorted.