Comb Sort
Comb sort is a sorting algorithm that improves upon the performance of bubble sort. It was first proposed by Włodzimierz Dobosiewicz in 1980 and later popularized by Stephen Lacey and Richard Box in their 1991 paper "Comb Sort: An Analysis."
The algorithm works by comparing and swapping adjacent elements that are a certain distance apart, known as the gap. The gap starts as the length of the input array and is divided by a shrink factor, typically 1.3. The process is repeated with successively smaller gap values until the gap becomes 1, at which point the algorithm reduces to a simple bubble sort.
By using a larger gap initially, Comb sort is able to move smaller elements towards the front of the array more quickly, which reduces the number of comparisons needed to sort the entire array. This results in a faster average case performance than bubble sort, with a time complexity of O(n^2) in the worst case, and O(n log n) in the best case.
Overall, Comb sort can be a useful sorting algorithm for small to medium-sized data sets, but it is generally outperformed by more advanced algorithms such as quicksort and merge sort for larger inputs.
Here given code implementation process.
// C Program
// Sort array elements by using Comb Sort
#include <stdio.h>
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
//Swapping the array elements of given location
void swap_element(int arr[], int first, int last)
{
int temp = arr[first];
arr[first] = arr[last];
arr[last] = temp;
}
//Perform the comb sort in given array
void comb_sort(int arr[], int size)
{
double shrink = 1.3;
//Loop controlling variable
int swapped = 0;
int i = 0;
//initial gap is equal to size of array
int gap = size;
// Loop, which is iterate array elements from front to end of array
// Until when swap operation are exist or gap is more than 1
while (gap != 1 || swapped == 1)
{
//Get a new gap
gap = (int)(gap / shrink);
if (gap < 1)
{
//When gap is less than 1
gap = 1;
}
i = 0;
//Set the swapped element status as false
swapped = 0;
while ((i + gap) < size)
{
if (arr[i] > arr[i + gap])
{
//Executing swap operation
swapped = 1;
//When need to swap array elements
swap_element(arr, i, i + gap);
}
i++;
}
}
}
int main()
{
//Define an sorted array of integers
int arr[] = {
8,
3,
8,
32,
-3,
1,
9,
23,
2,
4,
0,
5
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
//Before sort
printf("\n Before Sort :\n");
display(arr, size);
//Sort element
comb_sort(arr, size);
//After sort
printf("\n After Sort :\n");
display(arr, size);
return 0;
}Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32/*
Java Program
Sort array elements by using Comb Sort
*/
class MySort
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
//Swapping the array elements of given location
public void swap_element(int[] arr, int first, int last)
{
int temp = arr[first];
arr[first] = arr[last];
arr[last] = temp;
}
//Perform the comb sort in given array
public void comb_sort(int[] arr, int size)
{
double shrink = 1.3;
//Loop controlling variable
boolean swapped = false;
int i = 0;
//initial gap is equal to size of array
int gap = size;
// Loop, which is iterate array elements from front to end of array
// Until when swap operation are exist or gap is more than 1
while (gap != 1 || swapped == true)
{
//Get a new gap
gap = (int)(gap / shrink);
if (gap < 1)
{
//When gap is less than 1
gap = 1;
}
i = 0;
//Set the swapped element status as false
swapped = false;
while ((i + gap) < size)
{
if (arr[i] > arr[i + gap])
{
//Executing swap operation
swapped = true;
//When need to swap array elements
swap_element(arr, i, i + gap);
}
i++;
}
}
}
public static void main(String[] args)
{
MySort obj = new MySort();
//Define an sorted array of integers
int[] arr = {
8,
3,
8,
32,
-3,
1,
9,
23,
2,
4,
0,
5
};
//Get the size of array
int size = arr.length;
System.out.print("\n Before Sort :\n");
obj.display(arr, size);
//Sort element
obj.comb_sort(arr, size);
System.out.print("\n After Sort :\n");
obj.display(arr, size);
}
}Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32//Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Sort array elements by using Comb Sort
*/
class MySort
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
//Swapping the array elements of given location
void swap_element(int arr[], int first, int last)
{
int temp = arr[first];
arr[first] = arr[last];
arr[last] = temp;
}
//Perform the comb sort in given array
void comb_sort(int arr[], int size)
{
double shrink = 1.3;
//Loop controlling variable
bool swapped = false;
int i = 0;
//initial gap is equal to size of array
int gap = size;
// Loop, which is iterate array elements from front to end of array
// Until when swap operation are exist or gap is more than 1
while (gap != 1 || swapped == true)
{
//Get a new gap
gap = (int)(gap / shrink);
if (gap < 1)
{
//When gap is less than 1
gap = 1;
}
i = 0;
//Set the swapped element status as false
swapped = false;
while ((i + gap) < size)
{
if (arr[i] > arr[i + gap])
{
//Executing swap operation
swapped = true;
//When need to swap array elements
this->swap_element(arr, i, i + gap);
}
i++;
}
}
}
};
int main()
{
MySort obj = MySort();
int arr[] = {
8 , 3 , 8 , 32 , -3 , 1 , 9 , 23 , 2 , 4 , 0 , 5
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
cout << "\n Before Sort :\n";
obj.display(arr, size);
//Sort element
obj.comb_sort(arr, size);
cout << "\n After Sort :\n";
obj.display(arr, size);
return 0;
}Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32//Include namespace system
using System;
/*
C# Program
Sort array elements by using Comb Sort
*/
class MySort
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Swapping the array elements of given location
public void swap_element(int[] arr, int first, int last)
{
int temp = arr[first];
arr[first] = arr[last];
arr[last] = temp;
}
//Perform the comb sort in given array
public void comb_sort(int[] arr, int size)
{
double shrink = 1.3;
//Loop controlling variable
Boolean swapped = false;
int i = 0;
//initial gap is equal to size of array
int gap = size;
// Loop, which is iterate array elements from front to end of array
// Until when swap operation are exist or gap is more than 1
while (gap != 1 || swapped == true)
{
//Get a new gap
gap = (int)(gap / shrink);
if (gap < 1)
{
//When gap is less than 1
gap = 1;
}
i = 0;
//Set the swapped element status as false
swapped = false;
while ((i + gap) < size)
{
if (arr[i] > arr[i + gap])
{
//Executing swap operation
swapped = true;
//When need to swap array elements
swap_element(arr, i, i + gap);
}
i++;
}
}
}
public static void Main(String[] args)
{
MySort obj = new MySort();
int[] arr = {
8 , 3 , 8 , 32 , -3 , 1 , 9 , 23 , 2 , 4 , 0 , 5
};
//Get the size of array
int size = arr.Length;
Console.Write("\n Before Sort :\n");
obj.display(arr, size);
//Sort element
obj.comb_sort(arr, size);
Console.Write("\n After Sort :\n");
obj.display(arr, size);
}
}Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32<?php
/*
Php Program
Sort array elements by using Comb Sort
*/
class MySort
{
//Function which is display array elements
public function display( $arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo " ". $arr[$i];
}
echo "\n";
}
//Swapping the array elements of given location
public function swap_element( & $arr, $first, $last)
{
$temp = $arr[$first];
$arr[$first] = $arr[$last];
$arr[$last] = $temp;
}
//Perform the comb sort in given array
public function comb_sort( & $arr, $size)
{
$shrink = 1.3;
//Loop controlling variable
$swapped = false;
$i = 0;
//initial gap is equal to size of array
$gap = $size;
// Loop, which is iterate array elements from front to end of array
// Until when swap operation are exist or gap is more than 1
while ($gap != 1 || $swapped == true)
{
//Get a new gap
$gap = ((intval($gap / $shrink)));
if ($gap < 1)
{
//When gap is less than 1
$gap = 1;
}
$i = 0;
//Set the swapped element status as false
$swapped = false;
while (($i + $gap) < $size)
{
if ($arr[$i] > $arr[$i + $gap])
{
//Executing swap operation
$swapped = true;
//When need to swap array elements
$this->swap_element($arr, $i, $i + $gap);
}
$i++;
}
}
}
}
function main()
{
$obj = new MySort();
//Define an sorted array of integers
$arr = array(8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5);
//Get the size of array
$size = count($arr);
echo "\n Before Sort :\n";
$obj->display($arr, $size);
//Sort element
$obj->comb_sort($arr, $size);
echo "\n After Sort :\n";
$obj->display($arr, $size);
}
main();Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32/*
Node Js Program
Sort array elements by using Comb Sort
*/
class MySort
{
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//Swapping the array elements of given location
swap_element(arr, first, last)
{
var temp = arr[first];
arr[first] = arr[last];
arr[last] = temp;
}
//Perform the comb sort in given array
comb_sort(arr, size)
{
var shrink = 1.3;
//Loop controlling variable
var swapped = false;
var i = 0;
//initial gap is equal to size of array
var gap = size;
// Loop, which is iterate array elements from front to end of array
// Until when swap operation are exist or gap is more than 1
while (gap != 1 || swapped == true)
{
//Get a new gap
gap = ((parseInt(gap / shrink)));
if (gap < 1)
{
//When gap is less than 1
gap = 1;
}
i = 0;
//Set the swapped element status as false
swapped = false;
while ((i + gap) < size)
{
if (arr[i] > arr[i + gap])
{
//Executing swap operation
swapped = true;
//When need to swap array elements
this.swap_element(arr, i, i + gap);
}
i++;
}
}
}
}
function main()
{
var obj = new MySort();
//Define an sorted array of integers
var arr = [8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5];
//Get the size of array
var size = arr.length;
process.stdout.write("\n Before Sort :\n");
obj.display(arr, size);
//Sort element
obj.comb_sort(arr, size);
process.stdout.write("\n After Sort :\n");
obj.display(arr, size);
}
main();Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32# Python 3 Program
# Sort array elements by using Comb Sort
class MySort :
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
# Swapping the array elements of given location
def swap_element(self, arr, first, last) :
temp = arr[first]
arr[first] = arr[last]
arr[last] = temp
# Perform the comb sort in given array
def comb_sort(self, arr, size) :
shrink = 1.3
# Loop controlling variable
swapped = False
i = 0
# initial gap is equal to size of array
gap = size
# Loop, which is iterate array elements from front to end of array
# Until when swap operation are exist or gap is more than 1
while (gap != 1 or swapped == True) :
# Get a new gap
gap = ((int(gap / shrink)))
if (gap < 1) :
# When gap is less than 1
gap = 1
i = 0
# Set the swapped element status as false
swapped = False
while ((i + gap) < size) :
if (arr[i] > arr[i + gap]) :
# Executing swap operation
swapped = True
# When need to swap array elements
self.swap_element(arr, i, i + gap)
i += 1
def main() :
obj = MySort()
# Define an sorted array of integers
arr = [8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5]
# Get the size of array
size = len(arr)
print("\n Before Sort :\n", end = "")
obj.display(arr, size)
# Sort element
obj.comb_sort(arr, size)
print("\n After Sort :\n", end = "")
obj.display(arr, size)
if __name__ == "__main__": main()Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32# Ruby Program
# Sort array elements by using Comb Sort
class MySort
# Function which is display array elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
# Swapping the array elements of given location
def swap_element(arr, first, last)
temp = arr[first]
arr[first] = arr[last]
arr[last] = temp
end
# Perform the comb sort in given array
def comb_sort(arr, size)
shrink = 1.3
# Loop controlling variable
swapped = false
i = 0
# initial gap is equal to size of array
gap = size
# Loop, which is iterate array elements from front to end of array
# Until when swap operation are exist or gap is more than 1
while (gap != 1 || swapped == true)
# Get a new gap
gap = ((gap / shrink)).to_i
if (gap < 1)
# When gap is less than 1
gap = 1
end
i = 0
# Set the swapped element status as false
swapped = false
while ((i + gap) < size)
if (arr[i] > arr[i + gap])
# Executing swap operation
swapped = true
# When need to swap array elements
self.swap_element(arr, i, i + gap)
end
i += 1
end
end
end
end
def main()
obj = MySort.new()
# Define an sorted array of integers
arr = [8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5]
# Get the size of array
size = arr.length
print("\n Before Sort :\n")
obj.display(arr, size)
# Sort element
obj.comb_sort(arr, size)
print("\n After Sort :\n")
obj.display(arr, size)
end
main()Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32
/*
Scala Program
Sort array elements by using Comb Sort
*/
class MySort
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Swapping the array elements of given location
def swap_element(arr: Array[Int], first: Int, last: Int): Unit = {
var temp: Int = arr(first);
arr(first) = arr(last);
arr(last) = temp;
}
//Perform the comb sort in given array
def comb_sort(arr: Array[Int], size: Int): Unit = {
var shrink: Double = 1.3;
//Loop controlling variable
var swapped: Boolean = false;
var i: Int = 0;
//initial gap is equal to size of array
var gap: Int = size;
// Loop, which is iterate array elements from front to end of array
// Until when swap operation are exist or gap is more than 1
while (gap != 1 || swapped == true)
{
//Get a new gap
gap = (gap / shrink).toInt;
if (gap < 1)
{
//When gap is less than 1
gap = 1;
}
i = 0;
//Set the swapped element status as false
swapped = false;
while ((i + gap) < size)
{
if (arr(i) > arr(i + gap))
{
//Executing swap operation
swapped = true;
//When need to swap array elements
swap_element(arr, i, i + gap);
}
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MySort = new MySort();
//Define an sorted array of integers
var arr: Array[Int] = Array(8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5);
//Get the size of array
var size: Int = arr.length;
print("\n Before Sort :\n");
obj.display(arr, size);
//Sort element
obj.comb_sort(arr, size);
print("\n After Sort :\n");
obj.display(arr, size);
}
}Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32/*
Swift Program
Sort array elements by using Comb Sort
*/
class MySort
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Swapping the array elements of given location
func swap_element(_ arr: inout[Int], _ first: Int, _ last: Int)
{
let temp: Int = arr[first];
arr[first] = arr[last];
arr[last] = temp;
}
//Perform the comb sort in given array
func comb_sort(_ arr: inout [Int], _ size: Int)
{
let shrink: Double = 1.3;
//Loop controlling variable
var swapped: Bool = false;
var i: Int = 0;
//initial gap is equal to size of array
var gap: Int = size;
// Loop, which is iterate array elements from front to end of array
// Until when swap operation are exist or gap is more than 1
while (gap != 1 || swapped == true)
{
//Get a new gap
gap = Int(Double(gap) / shrink);
if (gap < 1)
{
//When gap is less than 1
gap = 1;
}
i = 0;
//Set the swapped element status as false
swapped = false;
while ((i + gap) < size)
{
if (arr[i] > arr[i + gap])
{
//Executing swap operation
swapped = true;
//When need to swap array elements
self.swap_element(&arr, i, i + gap);
}
i += 1;
}
}
}
}
func main()
{
let obj: MySort = MySort();
//Define an sorted array of integers
var arr: [Int] = [8, 3, 8, 32, -3, 1, 9, 23, 2, 4, 0, 5];
//Get the size of array
let size: Int = arr.count;
print("\n Before Sort :\n", terminator: "");
obj.display(arr, size);
//Sort element
obj.comb_sort(&arr, size);
print("\n After Sort :\n", terminator: "");
obj.display(arr, size);
}
main();Output
Before Sort :
8 3 8 32 -3 1 9 23 2 4 0 5
After Sort :
-3 0 1 2 3 4 5 8 8 9 23 32
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment