Implementation of Comb sort in C++

Hello Learners, Today in this tutorial we will learn about the Implementation of Comb Sort in C++. The concept behind the Comb Sort and Bubble Sort is almost the same or we can say that Comb Sort is an improvement or modification in the Bubble Sort algorithm. In the Bubble Sort algorithm, each element is compared with the next element in each iteration.

Comb Sort In C++

As Comb Sort is an improvised version of Bubble Sort it is because in comb sort we use a variable gap of size more than 1. Initially, the gap size will be equal to the size of the array. After each iteration, the gap size will decrease it will continue to be decreased until the gap value is 1. The shrink factor or decreasing factor or gap factor is empirically found to be 1.3 which means that after completing each iteration the gap is divided by 1.3.


Time Complexity

  • Best Case: O(n)                            //  Array is already sorted.
  • Average Case: O(n^2/2^p)      //  p is no of increment.
  • Worst Case: O(n^2)

Space Complexity: O(1)


ALGORITHM

  1. Create a variable gap and assign its value equal to the size of the array.
  2. Set  gap = int(gap/1.3)
  3. Iterate over the list or array from i = 0 to i < n-gap .
  4. If arr[i]  > arr[ i + gap ]  then  swap( arr[i] , arr[ i + gap] )  to arrange in the sorted array.
  5. Repeat this process while gap != 1.
#include<bits/stdc++.h> 
using namespace std; 

// Sorting Algorithm
int Comb_Sort(int arr[], int n) 
{ 
  int gap = n; 

  while (gap != 1) 
  { 
     // Shrink the gap factor by 1.3
    gap = int(gap/1.3); 
    if (gap < 1) 
       gap= 1;

    for (int i=0; i<n-gap; i++) 
    { 
      if (arr[i] > arr[i+gap]) 
        swap(arr[i], arr[i+gap]); 
    } 
  } 
} 
//main function

int main() 
{ 
  int arr[] = {21, 8, 32, -56, -41, 12, 23, 10, -28, 11, 54}; 
  
  // To find the no. of elements
  int n = sizeof(arr)/sizeof(arr[0]);          

  Comb_Sort(arr, n); 

    std::cout << "Unsorted Array" << std::endl;
    std::cout << "{21, 8, 32, -56, -41, 12, 23, 10, -28, 11, 54}"<< std::endl;
    std::cout << "Sorted Array" << std::endl;
    
  for (int i=0; i<n; i++) 
    std::cout << arr[i] <<" "; 

  return 0; 
} 

Output:

Unsorted Array                                                                                 
{21, 8, 32, -56, -41, 12, 23, 10, -28, 11, 54}                                                 
Sorted Array                                                                                   
-56 -41 -28 8 10 11 12 21 23 32 54

 

Leave a Reply

Your email address will not be published. Required fields are marked *