Posted on by Kalkicode
Code Sorting

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

Comment

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