Time and Space Complexity of Comb Sort

In this article, we will learn about Time Complexity and Space Complexity of Comb Sort algorithm, with the in-depth mathematical analysis of different cases. Comb Sort is also known as Dobosiewicz Sort.

In short,

• Time Complexity:-
  • O(n²) for the Worst Case
  • O(n²/2^p) for the Average Case, where, p is the number of increments.
  • O(nlog(n)) for the Best Case
• Space Complexity: O(1)

Index

• Comb Sort Algorithm in brief
• Analysing the Time Complexity for
  • Worst Case
  • Average Case
  • Best Case
• Analysing the Space Complexity
• Conclusion

Comb Sort Algorithm

The comb sort algorithm is an improved version of the bubble sort algorithm. The underlying idea of both the sorting algorithms is same. In the bubble sort method, the elements are compared with the succeeding elements. In the comb sort, the elements are sorted in a certain gap, decreasing the gap after each iteration by dividing the gap factor by the decreasing factor (also called the shrink factor) which is 1.3.

The pseudo-code for comb sort Algorithm is as follows:-

function combsort(array input) is

    gap := input.size
    shrink := 1.3
    sorted := false

    loop while sorted = false
        gap := floor(gap / shrink)
        if gap ≤ 1 then
            gap := 1
            sorted := true 
        end if
        i := 0
        loop while i + gap < input.size
            if input[i] > input[i+gap] then
                swap(input[i], input[i+gap])
                sorted := false
             end if

             i := i + 1
         end loop
     end loop
end function

• Python Code

  def getNextGap(gap):
  
      gap = (gap * 10)//13
      if gap < 1:
          return 1
      return gap
  
  def combSort(arr):
      n = len(arr)
  
      gap = n
  
      swapped = True
  
      while gap !=1 or swapped == 1:
  
          gap = getNextGap(gap)
  
          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  
      return arr
      
  array = [int(i) for i in input().split()]
  print(*combSort(array))  
  

• C++ Code

  #include <bits/stdc++.h>
  using namespace std;
  
  int getNextGap(int gap) {
      gap = (10 * gap)/13;
      if (gap < 1)
          return 1;
      return gap;
  }
  
  int* combSort(int a[], int n) {
      int gap = n;
      bool swapped = true;
      while (swapped==true or gap!=1) {
          gap = getNextGap(gap);
          swapped = false;
          for (int i=0; i<n-gap; i++) {
              if (a[i] > a[i+gap]) {
                  swap(a[i], a[i+gap]);
                  swapped = true;
              }
          }
      }
      return a;
  }
  
  int main() {
      int n;
      cin >> n;
      int arr[n];
      for (int i=0; i<n; i++) cin >> arr[i];
  
      int* sortedArr = combSort(arr, n);
      for (int i=0; i<n; i++) {
          cout << sortedArr[i] << ' ';
      }
      return 0;
  }  
  

Analysing the Time Complexity

The algorithm traverses 0^th to (n-gap)^th elements at each phase. The sequence of number of elements traversed is given as a_i at i^th phase,

a_i = n - floor( 10 * gap_i / 13 ) --> (1)

, where the gap is the gap at i^th phase.

gap_i = gap_i-1 - floor( 10 * gap_i-1 / 13 ) --> (2)

This implies that at i^th phase, the algorithm traverses a_i elements.

Worst Case
The Worst case configuration is when all the elements are already or nearly sorted but in reverse order. Calculating the upper bound of a_i from the equation (1) and recurrence relation (2) using a mathematical software for a worst case, we get a expression containing second and first degree terms of n with a constant giving the upper bound of n². Thus, the time complexity of a worst case is,

O(n²)

Average Case
The average case configuration is when a random order of elements are in the array. This configuration reduces the steps as some elements which are already sorted will not toggle the swapped variable's bool value and swap the numbers. Let the number of increments of phases be p and X be the sum of all the elements. Thus, X = ∑a_i. Estimating asymptotically,
np + (n−1)log((X+n-1)/(n-1)) + O(n) ≥ nlog(n) − Θ(n),
Therefore,
X ≥ (n²/(2^p)) Θ(1) = Ω(n²/(2^p))
Hence, the time complexity of an average case is,

O(n²/2^p)

Best Case
The best configuration occurs when all the elements are already sorted or nearly sorted. In this case, the loop with gap=1 will be run only once (as the others).
Sequences:-
a_n = n
a_n-1 = n/1.3
a_n-2 = n/(1.3)²
a_n-3 = n/(1.3)³
a_n-4 = n/(1.3)⁴
. . .
a_n-i = n/(1.3)ⁱ

S_n = a₁ + a₂ + ... + a_n

S_n = _r=1∑ⁿ (1/(1.3)^r)

Generalized Harmonic number is given as H_n,r.

H_n,r = _r=1∑ⁿ (1/k^r)

For,

n ≈ 1
H_n,1 ∈ O(log(n))

Since, we take k=1.3 approximately close to 1, the generalized harmonic number H_n,r

Θ ≈ O(nlog(n))

Therefore, the time complexity of the best case is,

O(nlog(n))

Analysing the space

Comb sort algorithm does not use any variable sized data structure or buffer nor make use of any recursive call, therefore, it takes O(1) space in all the cases.

Conclusion

The Comb sort algorithm is an improved version of bubble sort algorithm, which decreases the gap with a factor of 1.3 after every comparison. This algorithm takes time complexity of O(n²) for the worst case, O(n²/p²) for the average case, and O(nlog(n)) for the best case, with constant space complexity of O(1). Comb sort is better that bubble sort as it removes more than one inversion counts with one swap.

With this article at OpenGenus, you must have the complete idea of Time and Space Complexity of Comb Sort.