Comb Sort Program with Explanation and Code

2025-11-19 comb sort bubble sort optimization gap sort shrink factor sorting sorting algorithms python comb sort c comb sort javascript comb sort php comb sort csharp comb sort data structures

Comb Sort improves Bubble Sort by using a shrinking gap to eliminate slow element movement. This page explains the algorithm clearly and includes working programs in Python, C, JavaScript, PHP, and C#. Perfect for learning sorting optimizations.

Program Explanation

What is Comb Sort?

Comb Sort is an improvement over Bubble Sort that eliminates small values (turtles) near the end of the list by comparing elements that are far apart using a gap. The gap starts large and shrinks with each iteration. This helps Comb Sort achieve much better performance than Bubble Sort, especially for larger datasets.

Steps to Solve

  1. Initialize the gap as the length of the array.
  2. On every iteration, shrink the gap using the shrink factor (commonly 1.3).
  3. Compare elements that are gap positions apart.
  4. Swap them if they are in the wrong order.
  5. Continue until the gap becomes 1 and no swaps occur.
  6. The array is fully sorted once no swaps are needed with gap = 1.

Key Points

  • Faster than Bubble Sort due to larger initial comparisons.
  • Uses a shrink factor (default = 1.3, experimentally best).
  • Time complexity: O(n²) worst-case, O(n log n) average.
  • Simple and effective for medium-sized arrays.
  • Works in-place and uses no extra memory.

Program Code


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(0, n - gap):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                swapped = True

arr = list(map(int, input("Enter numbers: ").split()))
comb_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

int getNextGap(int gap) {
    gap = (gap * 10) / 13;
    return (gap < 1) ? 1 : gap;
}

void combSort(int arr[], int n) {
    int gap = n;
    int swapped = 1;

    while (gap != 1 || swapped) {
        gap = getNextGap(gap);
        swapped = 0;

        for (int i = 0; i < n - gap; i++) {
            if (arr[i] > arr[i + gap]) {
                int temp = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = temp;
                swapped = 1;
            }
        }
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    combSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function combSort(arr) {
  let n = arr.length;
  let gap = n;
  let shrink = 1.3;
  let swapped = true;

  while (gap > 1 || swapped) {
    gap = Math.floor(gap / shrink);
    if (gap < 1) gap = 1;

    swapped = false;

    for (let i = 0; i < n - gap; i++) {
      if (arr[i] > arr[i + gap]) {
        [arr[i], arr[i + gap]] = [arr[i + gap], arr[i]];
        swapped = true;
      }
    }
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
combSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static int GetNextGap(int gap) {
        gap = (gap * 10) / 13;
        return (gap < 1) ? 1 : gap;
    }

    static void CombSort(int[] arr) {
        int n = arr.Length;
        int gap = n;
        bool swapped = true;

        while (gap != 1 || swapped) {
            gap = GetNextGap(gap);
            swapped = false;

            for (int i = 0; i < n - gap; i++) {
                if (arr[i] > arr[i + gap]) {
                    int temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;
                    swapped = true;
                }
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        CombSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function getNextGap($gap) {
    $gap = intval($gap / 1.3);
    return ($gap < 1) ? 1 : $gap;
}

function combSort(&$arr) {
    $n = count($arr);
    $gap = $n;
    $swapped = true;

    while ($gap != 1 || $swapped) {
        $gap = getNextGap($gap);
        $swapped = false;

        for ($i = 0; $i < $n - $gap; $i++) {
            if ($arr[$i] > $arr[$i + $gap]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i + $gap];
                $arr[$i + $gap] = $temp;
                $swapped = true;
            }
        }
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
combSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1