Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
comb_sort.cpp File Reference

Comb Sort Algorithm (Comb Sort) More...

#include <algorithm>
#include <cassert>
#include <iostream>
Include dependency graph for comb_sort.cpp:

Functions

int FindNextGap (int gap)
 
void CombSort (int *arr, int l, int r)
 
void tests ()
 
int main ()
 

Detailed Description

Comb Sort Algorithm (Comb Sort)

Author
  • A better version of bubble sort algorithm
  • Bubble sort compares adjacent values whereas comb sort uses gap larger than 1
  • Best case Time complexity O(n) Worst case Time complexity O(n^2)

Function Documentation

◆ CombSort()

void CombSort ( int *  arr,
int  l,
int  r 
)

Function to sort array

Parameters
arrarray to be sorted
lstart index of array
rend index of array

initial gap will be maximum and the maximum possible value is the size of the array that is n and which is equal to r in this case so to avoid passing an extra parameter n that is the size of the array we are using r to initialize the initial gap.

Initialize swapped as true to make sure that loop runs

Keep running until gap = 1 or none elements were swapped

Find next gap

Compare all elements with current gap

42  {
43  /**
44  *
45  * initial gap will be maximum and the maximum possible value is
46  * the size of the array that is n and which is equal to r in this
47  * case so to avoid passing an extra parameter n that is the size of
48  * the array we are using r to initialize the initial gap.
49  *
50  */
51  int gap = r;
52 
53  /// Initialize swapped as true to make sure that loop runs
54  bool swapped = true;
55 
56  /// Keep running until gap = 1 or none elements were swapped
57  while (gap != 1 || swapped) {
58  /// Find next gap
59  gap = FindNextGap(gap);
60 
61  swapped = false;
62 
63  /// Compare all elements with current gap
64  for (int i = l; i <= r - gap; ++i) {
65  if (arr[i] > arr[i + gap]) {
66  std::swap(arr[i], arr[i + gap]);
67  swapped = true;
68  }
69  }
70  }
71 }
Here is the call graph for this function:

◆ FindNextGap()

int FindNextGap ( int  gap)

Find the next gap by shrinking the current gap by shrink factor of 1.3

Parameters
gapcurrent gap
Returns
new gap
29  {
30  gap = (gap * 10) / 13;
31 
32  return std::max(1, gap);
33 }
Here is the call graph for this function:

◆ main()

int main ( void  )

Main function

Running predefined tests

For user interaction

88  {
89  /// Running predefined tests
90  tests();
91 
92  /// For user interaction
93  int n;
94  std::cin >> n;
95  int *arr = new int[n];
96  for (int i = 0; i < n; ++i) std::cin >> arr[i];
97  CombSort(arr, 0, n);
98  for (int i = 0; i < n; ++i) std::cout << arr[i] << ' ';
99  delete[] arr;
100  return 0;
101 }
Here is the call graph for this function:

◆ tests()

void tests ( )

Test 1

Test 2

73  {
74  /// Test 1
75  int arr1[10] = {34, 56, 6, 23, 76, 34, 76, 343, 4, 76};
76  CombSort(arr1, 0, 10);
77  assert(std::is_sorted(arr1, arr1 + 10));
78  std::cout << "Test 1 passed\n";
79 
80  /// Test 2
81  int arr2[8] = {-6, 56, -45, 56, 0, -1, 8, 8};
82  CombSort(arr2, 0, 8);
83  assert(std::is_sorted(arr2, arr2 + 8));
84  std::cout << "Test 2 Passed\n";
85 }
Here is the call graph for this function:
FindNextGap
int FindNextGap(int gap)
Definition: comb_sort.cpp:29
std::is_sorted
T is_sorted(T... args)
CombSort
void CombSort(int *arr, int l, int r)
Definition: comb_sort.cpp:42
std::cout
std::swap
T swap(T... args)
std::max
T max(T... args)
std::cin
tests
void tests()
Definition: comb_sort.cpp:73