Comb Sort
An improved version of bubble sort that eliminates small values at the end of the list (turtles) by using a gap larger than 1.
Visualization
Details
Analogy
Imagine combing tangled hair. Instead of starting with fine teeth (like bubble sort comparing adjacent elements), you start with wide-toothed comb to remove major tangles, then gradually use finer combs. Each pass uses a smaller gap (tooth spacing) until you're comparing adjacent elements, by which time most elements are already nearly sorted.
Purpose
To sort an array more efficiently than bubble sort by comparing and swapping elements that are far apart, then progressively reducing the gap. This eliminates the 'turtle problem' where small values at the end take many iterations to move to the beginning.
Use Cases
Suitable for medium-sized datasets where bubble sort is too slow but more complex algorithms like quicksort aren't necessary. Often used in educational settings to demonstrate how simple modifications can significantly improve algorithm performance. Good for embedded systems with limited memory.
Algorithm Steps
function combSort(array):
n = length(array)
gap = n
shrink = 1.3
swapped = true
while gap > 1 or swapped:
gap = floor(gap / shrink)
if gap < 1: gap = 1
swapped = false
for i = 0 to n - gap - 1:
if array[i] > array[i + gap]:
swap(array[i], array[i + gap])
swapped = true
return array
Explanation
What's Happening?
Initial array: [8, 4, 1, 9, 2, 7, 3, 6]. Starting with gap = 8 / 1.3 ≈ 6.
Code Implementation
def comb_sort(arr):
n = len(arr)
gap = n
shrink = 1.3
swapped = True
while gap > 1 or swapped:
gap = int(gap / shrink)
if gap < 1:
gap = 1
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