Comb Sort

The pre-processing stage of Comb Sort is similar to the Shell Sort method. Comb sort is a significant advancement over bubble sort, and it is accomplished by pre-processing the data by integrating the comparison of the components’ step positions that are far apart from one another. It is a kind of comparison sorting algorithm.

The major mechanism included in this algorithm is each pair of adjacent elements is matched up and swapped if those elements are not arranged in an order.
This concept of sorting is called comb sort.

Decision tree for Comb Sort:

In the below decision tree “Y” indicates “yes”, “N” indicates “No” and “IMP” indicates “Impossible”.

Decision Tree for comb sort

Explanation: The above figure is implemented by applying the comb sort to make a decision tree.

Decision trees are carrying the l with “Y” and “N” which indicates “yes” and “no” respectively.
The major mechanism included in this algorithm is each pair of adjacent elements is matched up and swapped if those elements are not arranged in an order.
Leaves are the final value determined at the end of the tree which is notified with “[]” square brackets.
The above decision tree contains “24” leaves, which can be calculated by “n!” number of elements determined is “4”. Find the factorial value of four. This contains 24 leaves.
“IMP” indicates the impossible state, there is no leaf implemented after that.

Hence, this is the implementation decision tree by applying the comb sort.

C++

// C++ code for the above approach:
#include<bits/stdc++.h>
using namespace std;
void combSort(int arr[], int N){
   
  for (int turn = 0; turn < N - 1; turn++) {
    for (int j = 0; j < N - 1 - turn; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}
void printArr(int arr[], int N){
   
  for (int i = 0; i < N; i++) {
    cout << arr[i] << " ";
  }
}
 
// Drivers code
int main() {
  int arr[] = { 5, 4, 1, 3, 2 };
  int N = 5;
  combSort(arr, N);
  printArr(arr, N);
  return 0;
}

Java

// Java code for the above approach:
import java.util.*;
 
public class BasicSorting {
    public static void combSort(int arr[])
    {
        for (int turn = 0; turn < arr.length - 1; turn++) {
            for (int j = 0; j < arr.length - 1 - turn;
                 j++) {
                if (arr[j] > arr[j + 1]) {
 
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    public static void printArr(int arr[])
    {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
    // Drivers code
    public static void main(String args[])
    {
        int arr[] = { 5, 4, 1, 3, 2 };
        combSort(arr);
        printArr(arr);
    }
}

Python3

# Python code 
def comb_sort(arr):
   
    # loop to control number of passes
    for turn in range(len(arr) - 1):
       
        # loop to traverse each element and compare
        for j in range(len(arr) - 1 - turn):
            if arr[j] > arr[j + 1]:
                # Swap
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
 
def print_arr(arr):
    for i in arr:
        print(i, end=" ")
    print()
 
# Driver code
if __name__ == '__main__':
    arr = [5, 4, 1, 3, 2]
    comb_sort(arr)
    print_arr(arr)

C#

// C# code for the above approach:
using System;
 
public class BasicSorting {
    public static void CombSort(int[] arr)
    {
        for (int turn = 0; turn < arr.Length - 1; turn++) {
            for (int j = 0; j < arr.Length - 1 - turn;
                 j++) {
                if (arr[j] > arr[j + 1]) {
 
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
 
    public static void PrintArr(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[] arr = { 5, 4, 1, 3, 2 };
        CombSort(arr);
        PrintArr(arr);
    }
}
// This code is contributed by Prajwal Kandekar

Javascript

// JavaScript code for the above approach:
const combSort = (arr) => {
    for (let turn = 0; turn < arr.length - 1; turn++) {
        for (let j = 0; j < arr.length - 1 - turn; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
 
const printArr = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        console.log(arr[i] + " ");
    }
    console.log();
}
 
// Drivers code
const main = () => {
    let arr = [5, 4, 1, 3, 2];
    combSort(arr);
    printArr(arr);
}
 
main();

Output

1 2 3 4 5

Decision tree for Comb Sort:

C++

Java

Python3

C#

Javascript

Difference between Comb Sort and Shell Sort

Contact Us

Comb Sort

Decision tree for Comb Sort:

C++

Java

Python3

C#

Javascript

Difference between Comb Sort and Shell Sort

Similar Reads

Contact Us