1/20/25, 9:06 PM Comb Sort - javatpoint
Home Python Java JavaScript HTML SQL PHP C#
DS Tutorial
DS Tutorial
DS Introduction
DS Algorithm
Asymptotic Analysis
DS Pointer
DS Structure
DS Array
DS Array
2D Array
DS Linked List
Linked List
Types of Linked List
Singly Linked List
Doubly Linked List
Circular Linked List
Circular Doubly List
https://www.javatpoint.com/comb-sort 1/25
1/20/25, 9:06 PM Comb Sort - javatpoint
Skip list in DS
DS Stack
DS Stack
Array Implementation
← prev next →
Comb Sort Algorithm
In this article, we will discuss the comb sort Algorithm. Comb Sort is the advanced form of
bubble Sort. Bubble Sort compares all the adjacent values while comb sort removes all the
turtle values or small values near the end of the list.
It is a comparison-based sorting algorithm that is mainly an improvement in bubble sort. In
bubble sort, there is a comparison between the adjacent elements to sort the given array.
So, in bubble sort, the gap size between the elements that are compared is 1. Comb sort
improves the bubble sort by using a gap of size more than 1. The gap in the comb sort starts
with the larger value and then shrinks by a factor of 1.3. It means that after the completion
of each phase, the gap is divided by the shrink factor 1.3. The iteration continues until the
gap is 1.
The shrink factor is found to be 1.3 by testing comb sort on 200,000 random lists. Comb sort
works better than the bubble sort, but its time complexity in average case and worst case
remains O(n2).
The process of performing the comb sort is given as follows -
STEP 1 START
STEP 2 Calculate the gap value if gap value==1 goto step 5 else goto step 3
STEP 3 Iterate over data set and compare each item with gap item then goto step 4.
STEP 4 Swap the element if require else goto step 2
STEP 5 Print the sorted array.
https://www.javatpoint.com/comb-sort 2/25
1/20/25, 9:06 PM Comb Sort - javatpoint
STEP 6 STOP
Now, let's see the algorithm of comb sort.
Algorithm
combSort(array, n) // n is the size of array
gap = n // Initialize gap size equal to the size of array
shrink = 1.3 // gap shrink factor
swapped = true
while (gap ! = 1 || swapped = true)
gap = floor(gap/1.3);
if gap ≤ 1
gap = 1
end if
swapped = false
for every element range from 0 to n-gap, do the following -
if array[i] > array[i+gap]
swap(array[i], array[i+gap])
swapped = true
end if
end for loop
end while loop
end combSort
Working of comb Sort Algorithm
Now, let's see the working of the comb sort Algorithm.
To understand the working of the comb sort algorithm, let's take an unsorted array. It will
be easier to understand the comb sort via an example.
Let the elements of array are -
https://www.javatpoint.com/comb-sort 3/25
1/20/25, 9:06 PM Comb Sort - javatpoint
Now, initialize
n = 8 // size of array
gap = n
shrink = 1.3
swapped = true
First iteration
gap = floor(gap/shrink) = floor(8/1.3) = 6
swapped = false
This iteration ends here, because at i =2, the value of i + gap = 2 + 6 = 8, and there is no
element at 8th position of the array. So, after first iteration, the elements of array will be -
Now, move to iteration 2.
Second iteration
gap = floor(gap/shrink) = floor(6/1.3) = 4
swapped = false
https://www.javatpoint.com/comb-sort 4/25
1/20/25, 9:06 PM Comb Sort - javatpoint
This iteration ends here, because at i =4, the value of i + gap = 4 + 4 = 8, and there is no
element at 8th position of the array. So, after second iteration, the elements of array will be -
Now, move to iteration 3.
Third iteration
gap = floor(gap/shrink) = floor(4/1.3) = 3
swapped = false
This iteration ends here, because at i =5, the value of i + gap = 5 + 3 = 8, and there is no
element at 8th position of the array. So, after third iteration, the elements of array will be -
Now, move to iteration 4.
Fourth iteration
gap = floor(gap/shrink) = floor(3/1.3) = 2
swapped = false
https://www.javatpoint.com/comb-sort 5/25
1/20/25, 9:06 PM Comb Sort - javatpoint
This iteration ends here, because at i =6, the value of i + gap = 6 + 2 = 8, and there is no
element at 8th position of the array. So, after fourth iteration, the elements of array will be -
Now, move to iteration 5.
Fifth iteration
gap = floor(gap/shrink) = floor(2/1.3) = 1
swapped = false
After the fifth iteration, the sorted array is -
https://www.javatpoint.com/comb-sort 6/25
1/20/25, 9:06 PM Comb Sort - javatpoint
Hence, the iterations end here, and now the sorting is completed. Now, the final sorted
array is -
Comb sort complexity
Now, let's see the time complexity of Comb sort in the best case, average case, and worst
case. We will also see the space complexity of Comb sort.
1. Time Complexity
Case Time Complexity
Best Case θ(n log n)
Average Case Ω(n2/2p) where p is a number of
increments.
Worst Case O(n2)
Best Case Complexity - It occurs when there is no sorting required, i.e. the array
is already sorted. The best-case time complexity of comb sort is θ(n log n).
Average Case Complexity - It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending. The average
case time complexity of comb sort is Ω(n2/2p), where p is a number of
increments..
Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order. That means suppose you have to sort the array elements
in ascending order, but its elements are in descending order. The worst-case
time complexity of comb sort is O(n2).
2. Space Complexity
Space Complexity O(1)
https://www.javatpoint.com/comb-sort 7/25
1/20/25, 9:06 PM Comb Sort - javatpoint
Stable YES
The space complexity of comb sort is O(1).
Implementation of Comb sort
Now, let's see the programs of Comb sort in different programming languages.
Program: Write a program to implement comb sort in C language.
#include <stdio.h>
#include<math.h>
int updatedGap(int gap)
{
// Shrink gap by Shrink factor
gap = floor(gap/1.3);
if (gap < 1)
return 1;
return gap;
}
// Function to sort array elements using Comb Sort
void combSort(int a[], int n)
{
int gap = n; /* Initialize gap size equal to the size of array */
int swapped = 1;
while (gap != 1 || swapped == 1)
{
gap = updatedGap(gap); // find updated gap
// Initialize swapped as false so that we can
// check if swap happened or not
swapped = 0;
https://www.javatpoint.com/comb-sort 8/25
1/20/25, 9:06 PM Comb Sort - javatpoint
for (int i = 0; i < n-gap; i++) /* Compare all elements with current gap */
{
if (a[i] > a[i+gap]) //swap a[i] with a[i+gap]
{
int temp = a[i];
a[i] = a[i+gap];
a[i+gap] = temp;
swapped = 1;
}
}
}
}
void printArr(int a[], int n) /* function to print array elements */
{
for (int i=0; i<n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = {49, 11, 24, 44, 29, 27, 2};
int n = sizeof(a)/sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
combSort(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
Output
Program: Write a program to implement comb sort in C++.
https://www.javatpoint.com/comb-sort 9/25
1/20/25, 9:06 PM Comb Sort - javatpoint
#include <iostream>
#include<cmath>
using namespace std;
int updatedGap(int gap)
{
// Shrink gap by Shrink factor
gap = floor(gap/1.3);
if (gap < 1)
return 1;
return gap;
}
// Function to sort array elements using Comb Sort
void combSort(int a[], int n)
{
int gap = n; /* Initialize gap size equal to the size of array */
int swapped = 1;
while (gap != 1 || swapped == 1)
{
gap = updatedGap(gap); // find updated gap
// Initialize swapped as false so that we can
// check if swap happened or not
swapped = 0;
for (int i = 0; i < n-gap; i++) /* Compare all elements with current gap */
{
if (a[i] > a[i+gap]) //swap a[i] with a[i+gap]
{
int temp = a[i];
a[i] = a[i+gap];
a[i+gap] = temp;
swapped = 1;
https://www.javatpoint.com/comb-sort 10/25
1/20/25, 9:06 PM Comb Sort - javatpoint
}
}
}
}
void printArr(int a[], int n) /* function to print array elements */
{
for (int i=0; i<n; i++)
cout<<a[i]<<" ";
}
int main()
{
int a[] = {48, 10, 23, 43, 28, 26, 1};
int n = sizeof(a)/sizeof(a[0]);
cout<<"Before sorting array elements are - \n";
printArr(a, n);
combSort(a, n);
cout<<"\nAfter sorting array elements are - \n";
printArr(a, n);
return 0;
}
Output
Program: Write a program to implement comb sort in C#.
using System;
class CombSort {
static int updatedGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;
if (gap < 1)
https://www.javatpoint.com/comb-sort 11/25
1/20/25, 9:06 PM Comb Sort - javatpoint
return 1;
return gap;
}
// Function to sort array elements using Comb Sort
static void combSort(int[] a, int n)
{
int gap = n; /* Initialize gap size equal to the size of array */
int swapped = 1;
while (gap != 1 || swapped == 1)
{
gap = updatedGap(gap); // find updated gap
// Initialize swapped as false so that we can
// check whether swap happened or not
swapped = 0;
for (int i = 0; i < n-gap; i++) /* Compare all elements with current gap */
{
if (a[i] > a[i+gap]) //swap a[i] with a[i+gap]
{
int temp = a[i];
a[i] = a[i+gap];
a[i+gap] = temp;
swapped = 1;
}
}
}
}
static void printArr(int[] a, int n) /* function to print array elements */
{
for (int i=0; i<n; i++)
Console.Write(a[i] + " ");
}
static void Main() {
https://www.javatpoint.com/comb-sort 12/25
1/20/25, 9:06 PM Comb Sort - javatpoint
int[] a = {44, 40, 14, 43, 28, 26, 1, 5, 9};
int n = a.Length;
Console.Write("Before sorting array elements are - \n");
printArr(a, n);
combSort(a, n);
Console.Write("\nAfter sorting array elements are - \n");
printArr(a, n);
}
}
Output
Program: Write a program to implement comb sort in Java.
class CombSort {
static int updatedGap(int gap)
{
// Shrink gap by Shrink factor
gap = (gap*10)/13;
if (gap < 1)
return 1;
return gap;
}
// Function to sort array elements using Comb Sort
static void combSort(int a[], int n)
{
int gap = n; /* Initialize gap size equal to the size of array */
int swapped = 1;
while (gap != 1 || swapped == 1)
https://www.javatpoint.com/comb-sort 13/25
1/20/25, 9:06 PM Comb Sort - javatpoint
{
gap = updatedGap(gap); // find updated gap
// Initialize swapped as false so that we can
// check whether swap happened or not
swapped = 0;
for (int i = 0; i < n-gap; i++) /* Compare all elements
with current gap */
{
if (a[i] > a[i+gap]) //swap a[i] with a[i+gap]
{
int temp = a[i];
a[i] = a[i+gap];
a[i+gap] = temp;
swapped = 1;
}
}
}
}
static void printArr(int a[], int n) /* function to print array elements */
{
for (int i=0; i<n; i++)
System.out.print(a[i] + " ");
}
public static void main(String args[]) {
int[] a = {43, 39, 13, 42, 27, 25, 0, 4, 8};
int n = a.length;
System.out.print("\nBefore sorting array elements are - ");
printArr(a, n);
combSort(a, n);
System.out.print("\nAfter sorting array elements are - ");
printArr(a, n);
System.out.println();
https://www.javatpoint.com/comb-sort 14/25
1/20/25, 9:06 PM Comb Sort - javatpoint
}
}
Output
Program: Write a program to implement comb sort in PHP.
<?php
function updatedGap($gap)
{
// Shrink gap by Shrink factor
$gap = ($gap*10)/13;
if ($gap < 1)
return 1;
return $gap;
}
// Function to sort array elements using Comb Sort
function combSort(&$a, $n)
{
$gap = $n; /* Initialize gap size equal to the size of array */
$swapped = 1;
while ($gap != 1 || $swapped == 1)
{
$gap = updatedGap($gap); // find updated gap
// Initialize swapped as false so that we can
// check whether swap happened or not
$swapped = 0;
for ($i = 0; $i < $n-$gap; $i++) /* Compare all elements with current gap */
{
https://www.javatpoint.com/comb-sort 15/25
1/20/25, 9:06 PM Comb Sort - javatpoint
if ($a[$i] > $a[$i+$gap]) //swap a[i] with a[i+gap]
{
$temp = $a[$i];
$a[$i] = $a[$i+$gap];
$a[$i+$gap] = $temp;
$swapped = 1;
}
}
}
}
function printArr($a, $n) /* function to print array elements */
{
for($i = 0; $i < $n; $i++)
{
print_r($a[$i]);
echo " ";
}
}
$a = array(44, 40, 14, 43, 28, 26, 1, 5, 9);
$n = count($a);
echo "Before sorting array elements are - <br>";
printArr($a, $n);
combSort($a,$n);
echo "<br> After sorting array elements are - <br>";
printArr($a, $n);
?>
Output
So, that's all about the article. Hope the article will be helpful and informative to you.
https://www.javatpoint.com/comb-sort 16/25
1/20/25, 9:06 PM Comb Sort - javatpoint
This article was not only limited to the algorithm. Along with the algorithm, we have also
discussed the Comb Sort's complexity, working, and implementation in different
programming languages.
Next Topic Counting Sort
← prev next →
Related Posts
Merge Sort
Algorithm In this article, we will discuss the merge sort Algorithm. Merge sort is the sorting
technique that follows the divide and conquer approach. This article will be very helpful
and interesting to students as they might face merge sort as a question in their
examinations....
17 min read
Cycle Sort
Cycle sort algorithm In this article, we will discuss the Cycle sort Algorithm. Cycle sort is a
comparison sorting algorithm that forces array to be factored into the number of cycles
where each of them can be rotated to produce a sorted array. It is theoretically optimal...
16 min read
Counting Sort
Algorithm In this article, we will discuss the counting sort Algorithm. Counting sort is a
sorting technique that is based on the keys between specific ranges. In coding or technical
interviews for software engineers, sorting algorithms are widely asked. So, it is important to
discuss the...
https://www.javatpoint.com/comb-sort 17/25
1/20/25, 9:06 PM Comb Sort - javatpoint
10 min read
Quick Sort
Algorithm In this article, we will discuss the Quicksort Algorithm. The working procedure of
Quicksort is also simple. This article will be very helpful and interesting to students as they
might face quicksort as a question in their examinations. So, it is important to discuss the...
10 min read
Tim Sort
Algorithm In this article, we will discuss the Tim sort Algorithm. Tim-sort is a sorting
algorithm derived from insertion sort and merge sort. It was designed to perform optimally
on different kind of real-world data. Tim sort is an adaptive sorting algorithm that needs
O(n log n)...
15 min read
Cocktail Sort
Algorithm In this article, we will discuss the cocktail sort algorithm. Cocktail sort is the
variation of Bubble Sort, which traverses the list in both directions alternatively. It is
different from bubble sort in the sense that bubble sort traverses the list in the forward
direction...
10 min read
Sorting Algorithms
Sorting is the process of arranging the elements of an array so that they can be placed
either in ascending or descending order. For example, consider an array A = {A1, A2, A3, A4,
?? An }, the array is called to be in ascending...
3 min read
https://www.javatpoint.com/comb-sort 18/25
1/20/25, 9:06 PM Comb Sort - javatpoint
Radix Sort
Algorithm In this article, we will discuss the Radix sort Algorithm. Radix sort is the linear
sorting algorithm that is used for integers. In Radix sort, there is digit by digit sorting is
performed that is started from the least significant digit to the most significant...
9 min read
Shell Sort
Algorithm In this article, we will discuss the shell sort algorithm. Shell sort is the
generalization of insertion sort, which overcomes the drawbacks of insertion sort by
comparing elements separated by a gap of several positions. It is a sorting algorithm that is
an extended version of...
7 min read
Bitonic Sort
Algorithm In this article, we will discuss the Bitonic sort Algorithm. Bitonic sort is a parallel
sorting algorithm that performs O(n2log n) comparisons. Although the number of
comparisons is more than that in any other popular sorting algorithm, it performs better
for the parallel implementation because...
12 min read
Learn Important Tutorial
Python Java
https://www.javatpoint.com/comb-sort 19/25
1/20/25, 9:06 PM Comb Sort - javatpoint
Javascript HTML
Database PHP
C++ React
B.Tech / MCA
Data
DBMS
Structures
Operating
DAA
System
https://www.javatpoint.com/comb-sort 20/25
1/20/25, 9:06 PM Comb Sort - javatpoint
Computer Compiler
Network Design
Computer Discrete
Organization Mathematics
Ethical Computer
Hacking Graphics
Web Software
Technology Engineering
Cyber
Automata
Security
https://www.javatpoint.com/comb-sort 21/25
1/20/25, 9:06 PM Comb Sort - javatpoint
C
Programming
C++
Java .Net
Python Programs
Control Data
System Warehouse
Preparation
Aptitude Reasoning
https://www.javatpoint.com/comb-sort 22/25
1/20/25, 9:06 PM Comb Sort - javatpoint
Verbal Interview
Ability Questions
Company
Questions
https://www.javatpoint.com/comb-sort 23/25
1/20/25, 9:06 PM Comb Sort - javatpoint
https://www.javatpoint.com/comb-sort 24/25
1/20/25, 9:06 PM Comb Sort - javatpoint
https://www.javatpoint.com/comb-sort 25/25
