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

arr	array to be sorted
l	start index of array
r	end 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

                                      {
    /**
     *
     * 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.
     *
     */
    int gap = r;
 
    /// Initialize swapped as true to make sure that loop runs
    bool swapped = true;
 
    /// Keep running until gap = 1 or none elements were swapped
    while (gap != 1 || swapped) {
        /// Find next gap
        gap = FindNextGap(gap);
 
        swapped = false;
 
        /// Compare all elements with current gap
        for (int i = l; i < r - gap; ++i) {
            if (arr[i] > arr[i + gap]) {
                std::swap(arr[i], arr[i + gap]);
                swapped = true;
            }
        }
    }
}

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

gap	current gap

Returns

new gap

                         {
    gap = (gap * 10) / 13;
 
    return std::max(1, gap);
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function

Running predefined tests

For user interaction

           {
    /// Running predefined tests
    tests();
 
    /// For user interaction
    int n;
    std::cin >> n;
    int *arr = new int[n];
    for (int i = 0; i < n; ++i) std::cin >> arr[i];
    CombSort(arr, 0, n);
    for (int i = 0; i < n; ++i) std::cout << arr[i] << ' ';
    delete[] arr;
    return 0;
}

Here is the call graph for this function:

tests()

void tests

(

)

Test 1

Test 2

             {
    /// Test 1
    int arr1[10] = {34, 56, 6, 23, 76, 34, 76, 343, 4, 76};
    CombSort(arr1, 0, 10);
    assert(std::is_sorted(arr1, arr1 + 10));
    std::cout << "Test 1 passed\n";
 
    /// Test 2
    int arr2[8] = {-6, 56, -45, 56, 0, -1, 8, 8};
    CombSort(arr2, 0, 8);
    assert(std::is_sorted(arr2, arr2 + 8));
    std::cout << "Test 2 Passed\n";
}

Here is the call graph for this function: