Explanation
- Comb Sort is a variation of Bubble Sort that improves on it by using a gap sequence. It eliminates small values near the end of the list more quickly by using a larger gap between comparisons.
Steps:
- Start with a large gap, typically about 1.3 times the size of the list.
- Compare elements that are
gappositions apart. - Reduce the gap after each pass and continue sorting.
Time Complexity:
- Worst Case: O(n^2).
def comb_sort(arr):
n = len(arr)
gap = n
swapped = True
while gap > 1 or swapped:
gap = max(1, int(gap / 1.3))
swapped = False
for i in range(n - gap):
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap] = arr[i + gap], arr[i]
swapped = True
return arr
# Example usage
arr = [5, 2, 9, 1, 5, 6]
print("Sorted array is:", comb_sort(arr))