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?
The Comb Sort algorithm 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.
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));
}
}