# Comb Sort Algorithm

## Introduction to Comb Sort

Comb sort is an improvement over bubble sort. It eliminates small values near the end of the list that slow down the sorting process. Comb sort works by comparing and swapping elements separated by a gap, which reduces progressively until the list is sorted. The algorithm aims to reduce the number of comparisons by jumping over multiple elements in each pass.

## Step-by-Step Process

Consider an array with the following elements:

```
[8, 4, 1, 56, 3, -44, 23, -6, 28, 0]
```

To sort this array using comb sort, follow these steps:

**Initialize Gap**: Set the initial gap to the length of the array divided by 1.3 (Shrink factor). Continue until the gap is 1.**Compare and Swap**: Compare elements that are a gap distance apart. If they are out of order, swap them.**Reduce Gap**: Reduce the gap for the next pass. Typically, the gap is divided by 1.3.**Repeat**: Repeat the process until the gap is 1 and the array is sorted.

Let's apply these steps to the example array:

- Initial gap: 10 / 1.3 = 7
- First Pass with gap 7: [8, 4, 1, 56, 3, -44, 23, -6, 28, 0] -> [8, 4, 1, -6, 3, -44, 23, 56, 28, 0]
- Second Pass with gap 5: [8, 4, 1, -6, 3, -44, 23, 56, 28, 0] -> [8, 4, 1, -6, 0, -44, 23, 56, 28, 3]
- Third Pass with gap 3: [8, 4, 1, -6, 0, -44, 23, 56, 28, 3] -> [8, 4, -44, -6, 0, 1, 23, 56, 28, 3]
- Fourth Pass with gap 2: [8, 4, -44, -6, 0, 1, 23, 56, 28, 3] -> [8, -6, -44, 0, 4, 1, 23, 3, 28, 56]
- Fifth Pass with gap 1: [8, -6, -44, 0, 4, 1, 23, 3, 28, 56] -> [-6, -44, 0, 1, 3, 4, 8, 23, 28, 56]

## Pseudo Code for Comb Sort

Below is the pseudo code for the comb sort algorithm:

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

Explanation:

**Initialize**: The function starts by determining the length of the array and setting the initial gap to n. The shrink factor is typically set to 1.3.**Gap Reduction**: The gap is reduced by dividing it by the shrink factor. If the gap becomes less than or equal to 1, it is set to 1, and the sorted flag is set to true.**Comparison and Swap**: Elements separated by the current gap are compared and swapped if they are out of order. If a swap occurs, the sorted flag is set to false.**Repeat**: The process repeats until the gap is 1 and the array is sorted.

## Python Program to Implement Comb Sort

```
def comb_sort(arr):
n = len(arr)
gap = n
shrink = 1.3
sorted = False
while not sorted:
gap = int(gap / shrink)
if gap <= 1:
gap = 1
sorted = True
i = 0
while i + gap < n:
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap] = arr[i + gap], arr[i]
sorted = False
i += 1
return arr
# Example usage:
array = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]
print("Original array:", array)
sorted_array = comb_sort(array)
print("Sorted array:", sorted_array) # Output: [-44, -6, 0, 1, 3, 4, 8, 23, 28, 56]
```

This Python program defines a function to perform comb sort on an array. The function initializes the gap and progressively reduces it while comparing and swapping elements until the array is sorted.