How To Do Comb Sort in Python

Introduction

Comb sort is a relatively simple yet efficient comparison-based sorting algorithm that improves bubble sort by eliminating turtles (small values at the end of the list) early on. It introduces a gap between compared elements, gradually shrinking throughout the sorting process. In this blog post, we’ll explain how comb sort works, provide a Python implementation, and discuss its advantages and limitations compared to algorithms like bubble sort and quick sort.

---

What is Comb Sort?

Comb sort is an enhanced version of bubble sort that improves performance by focusing on eliminating turtles early on. Turtles are small elements near the end of the array that cause inefficiencies in bubble sort because they take many passes to move to their correct positions. Comb sort achieves this by introducing a gap between compared elements, which gradually shrinks throughout the sorting process. Rabbits (large elements near the start of the array) are naturally moved to the end more quickly and don’t present as much of a problem.

Key points about comb sort

• It starts with a gap that is a large fraction of the array size.
• The gap is reduced with each pass, and the list is eventually sorted when the gap becomes 1 (similar to bubble sort).
• Comb sort is not a stable sorting algorithm.

How Comb Sort Works

• Initialize a gap (initially the size of the array).
• Compare elements that are a “gap” apart and swap them if needed.
• Shrink the gap using a shrink factor (commonly set to 1.3).
• Repeat the process until the gap becomes 1, at this point, the algorithm behaves like bubble sort to ensure the array is fully sorted.

Comb Sort Pseudocode

CombSort(array):
    n = length of array
    gap = n
    shrink_factor = 1.3
    sorted = false

    while sorted is false:
        # Step 1: Update the gap
        gap = gap / shrink_factor
        if gap < 1:
            gap = 1

        # Step 2: Assume the array is sorted
        sorted = true

        # Step 3: Compare elements that are gap apart
        for i = 0 to (n - gap - 1):
            if array[i] > array[i + gap]:
                # Step 4: Swap elements if out of order
                swap(array[i], array[i + gap])
                sorted = false  # If a swap happens, the array is not fully sorted

Key Steps in the Pseudocode:

1. Initialize gap: The gap is initially set to the size of the array.
2. Gap reduction: The gap is reduced by dividing it by a shrink factor (typically 1.3).
3. Element comparison and swapping: Compare elements that are gap positions apart and swap them if they are in the wrong order.
4. Repeat until sorted: The process continues until no swaps are needed when the gap is reduced to 1, at which point the array is fully sorted.

Time Complexity of Comb Sort

• Best Case: O(n log n)
• Average Case: O(n²/2^p) (better than bubble sort)
• Worst Case: O(n²)

Space Complexity of Comb Sort

• O(1) as it is an in-place sorting algorithm.

---

Comb Sort Algorithm in Python

Here’s a Python implementation of comb sort:

def comb_sort(arr):
    # Step 1: Initialize the gap and shrink factor
    n = len(arr)
    gap = n
    shrink_factor = 1.3
    sorted = False

    # Step 2: Continue until the gap becomes 1 and no swaps are needed
    while not sorted:
        # Update the gap
        gap = int(gap / shrink_factor)
        if gap < 1:
            gap = 1
        
        sorted = True  # Assume the array is sorted

        # Step 3: Compare elements that are 'gap' apart
        for i in range(n - gap):
            if arr[i] > arr[i + gap]:
                # Swap if needed
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                sorted = False  # If a swap occurs, continue sorting

# Example usage
data = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]
comb_sort(data)
print("Sorted array:", data)

Output:

Sorted array: [-44, -6, 0, 1, 3, 4, 8, 23, 28, 56]

---

Step-by-Step Explanation of Comb Sort

Let’s break down how comb sort works for the array [8, 4, 1, 56, 3, -44, 23, -6, 28, 0].

Step 1: Initialize the Gap

• The initial gap is set to the length of the array, which is 10. We then shrink the gap using a shrink factor (commonly 1.3). Since the gap is the length of the array, there are no comparisons in the first pass.

Initial array:

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

Step 2: Shrink the Gap

• After the first pass, we reduce the gap by dividing it by the shrink factor (1.3), rounding down the result to an integer. Now, the gap becomes int(10 / 1.3) = 7.

Gap after shrinking: 7

• Now we compare elements that are 7 positions apart:
  • Compare arr[0] (8) and arr[7] (-6): Swap.
  • Compare arr[1] (4) and arr[8] (28): No swap.
  • Compare arr[2] (1) and arr[9] (0): Swap.

Array after first pass:

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

Step 3: Shrink the Gap Again

• We reduce the gap again: int(7 / 1.3) = 5.

Gap after shrinking: 5

• Compare elements that are 5 positions apart:
  • Compare arr[0] (-6) and arr[5] (-44): Swap.
  • Compare arr[1] (4) and arr[6] (23): No swap.
  • Compare arr[2] (0) and arr[7] (8): No swap.
  • Compare arr[3] (56) and arr[8] (28): Swap.
  • Compare arr[4] (3) and arr[9] (1): Swap.

Array after second pass:

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

Step 4: Shrink the Gap Again

• We shrink the gap further: int(5 / 1.3) = 3.

Gap after shrinking: 3

• Compare elements that are 3 positions apart:
  • Compare arr[0] (-44) and arr[3] (28): No swap.
  • Compare arr[1] (4) and arr[4] (1): Swap.
  • Compare arr[2] (0) and arr[5] (-6): Swap.
  • Compare arr[3] (28) and arr[6] (23): Swap.
  • Compare arr[4] (4) and arr[7] (8): No swap.
  • Compare arr[5] (0) and arr[8] (56): No swap.
  • Compare arr[6] (28) and arr[9] (3): Swap.

Array after third pass:

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

Step 5: Shrink the Gap Again

• Reduce the gap again: int(3 / 1.3) = 2.

Gap after shrinking: 2

• Compare elements that are 2 positions apart:
  • Compare arr[0] (-44) and arr[2] (-6): No swap.
  • Compare arr[1] (1) and arr[3] (23): No swap.
  • Compare arr[2] (-6) and arr[4] (4): No swap.
  • Compare arr[3] (23) and arr[5] (0): Swap.
  • Compare arr[4] (4) and arr[6] (3): Swap.
  • Compare arr[5] (23) and arr[7] (8): Swap.
  • Compare arr[6] (23) and arr[8] (56): No swap.
  • Compare arr[7] (8) and arr[9] (28): No swap.

Array after fourth pass:

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

Step 6: Shrink the Gap to 1 (Bubble Sort Pass)

• Finally, shrink the gap to 1, at which point comb sort behaves like bubble sort.

Gap after shrinking: 1

• Perform adjacent comparisons:
  • Compare arr[0] (-44) and arr[1] (1): No swap.
  • Compare arr[1] (1) and arr[2] (-6): Swap.
  • Compare arr[2] (1) and arr[3] (0): Swap.
  • Compare arr[3] (1) and arr[4] (3): No swap.
  • Compare arr[4] (3) and arr[5] (4): No swap.
  • Compare arr[5] (4) and arr[6] (8): No swap.
  • Compare arr[6] (8) and arr[7] (23): No swap.
  • Compare arr[7] (23) and arr[8] (56): No swap.
  • Compare arr[8] (56) and arr[9] (28): Swap.

Array after final pass:

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

Final Sorted Array

After the final pass with a gap of 1, the array is fully sorted:

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

---

Comb Sort vs. Other Sorting Algorithms

Comb Sort vs. Bubble Sort

• Performance: Comb sort improves upon bubble sort by eliminating turtles early on. Bubble sort has O(n²) time complexity in the worst case, while comb sort can reduce that to O(n log n) in the best case.
• Gap Reduction: Unlike bubble sort, which only compares adjacent elements, comb sort starts by comparing elements far apart, reducing inefficiencies caused by small values near the end of the list.

Comb Sort vs. Quick Sort

• Performance: Quick sort is generally faster, with an average time complexity of O(n log n), but has a worst-case time complexity of O(n²). Comb sort, while better than bubble sort, typically has an O(n²) time complexity in the worst case.
• Stability: Neither quicksort nor comb sort is stable. Stability refers to preserving the relative order of equal elements.

Comb Sort vs. Insertion Sort

• Performance: Insertion sort performs well on small or nearly sorted arrays, with a time complexity of O(n²) in the average case. However, comb sort is more efficient for larger datasets due to the initial wide gap comparisons.
• Adaptability: Insertion sort is an adaptive algorithm, meaning it performs better on nearly sorted data. Comb sort, on the other hand, shines when the data is more unordered due to its ability to remove large out-of-order elements quickly.

---

Advantages of Comb Sort

1. Better Than Bubble Sort: Comb sort is a significant improvement over bubble sort because it reduces the inefficiencies of comparing adjacent elements early in the sorting process.
2. Simple and In-Place: Like bubble sort, comb sort is easy to understand and implement. It is also an in-place algorithm, meaning it doesn’t require extra space beyond the input array.
3. Handles Turtles Efficiently: By starting with a large gap, comb sort efficiently handles turtles, which are small elements near the end of the list that cause inefficiencies in bubble sort.

---

Limitations of Comb Sort

1. Not Stable: Comb sort is not a stable sorting algorithm. This means that it does not preserve the relative order of equal elements in the input array.
2. Not as Fast as Quick sort or Merge Sort: Although comb sort is more efficient than bubble sort, it is generally not as fast as algorithms like quick sort, heap sort, or merge sort, which have a consistent O(n log n) time complexity.
3. Worst-Case Time Complexity: While comb sort can approach O(n log n) in the best case, its worst-case performance is still O(n²), making it less efficient for large datasets compared to other algorithms.

---

When to Use Comb Sort

• Improvement over Bubble Sort: If you’re using bubble sort and want a simple improvement in performance, comb sort is a great choice. It shares much of the simplicity of bubble sort but is more efficient due to its gap-based comparisons.
• Medium-Sized Datasets: Comb sort is best suited for small to medium-sized datasets where the overhead of more complex algorithms like quicksort or mergesort may not be justified.
• Simple Implementation: When you need a simple, easy-to-implement sorting algorithm that performs better than basic algorithms like bubble sort or insertion sort, comb sort can be a good option.

---

Conclusion

Comb sort offers an efficient alternative to bubble sort by eliminating turtles early through a gap-based comparison strategy. Although it may not outperform advanced algorithms like quick sort or merge sort in most cases, comb sort’s simplicity and performance make it an excellent choice for specific use cases. Try the Python implementation above to see how comb sort performs on your data and explore its benefits over other basic sorting algorithms.

Congratulations on reading to the end of this tutorial!

For further reading on sorting algorithms in Python, go to the articles:

• How to do Insertion Sort in Python
• How to Do Bubble Sort in Python
• How to Do Selection Sort in Python
• How to Do Bucket Sort in Python
• How to Do Heap Sort in Python
• How to Do Pigeonhole Sort in Python

Go to the online courses page on Python to learn more about Python for data  science and  machine learning.

Have fun and happy researching!