gnome_sort.cpp File Reference

Implementation of gnome sort algorithm. More...

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>

Include dependency graph for gnome_sort.cpp:

Namespaces
namespace	sorting
	for working with vectors

Functions
template<typename T >
void	sorting::gnomeSort (T *arr, int size)
template<typename T , size_t size>
std::array< T, size >	sorting::gnomeSort (std::array< T, size > arr)
static void	test ()
int	main ()

Detailed Description

Implementation of gnome sort algorithm.

Author

beqakd

Krishna Vedala

Gnome sort algorithm is not the best one but it is widely used. The algorithm iteratively checks the order of pairs in the array. If they are on right order it moves to the next successive pair, otherwise it swaps elements. This operation is repeated until no more swaps are made thus indicating the values to be in ascending order.

The time Complexity of the algorithm is \(O(n^2)\) and in some cases it can be \(O(n)\).

Function Documentation

main()

int main

(

void

)

Our main function with example of sort method.

           {
    test();
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Test function

                   {
    // Example 1. Creating array of int,
    std::cout << "Test 1 - as a C-array...";
    const int size = 6;
    std::array<int, size> arr = {-22, 100, 150, 35, -10, 99};
    sorting::gnomeSort(arr.data(),
                       size);  // pass array data as a C-style array pointer
    assert(std::is_sorted(std::begin(arr), std::end(arr)));
    std::cout << " Passed\n";
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << ", ";
    }
    std::cout << std::endl;
 
    // Example 2. Creating array of doubles.
    std::cout << "\nTest 2 - as a std::array...";
    std::array<double, size> double_arr = {-100.2, 10.2, 20.0, 9.0, 7.5, 7.2};
    std::array<double, size> sorted_arr = sorting::gnomeSort(double_arr);
    assert(std::is_sorted(std::begin(sorted_arr), std::end(sorted_arr)));
    std::cout << " Passed\n";
    for (int i = 0; i < size; i++) {
        std::cout << double_arr[i] << ", ";
    }
    std::cout << std::endl;
 
    // Example 3. Creating random array of float.
    std::cout << "\nTest 3 - 200 random numbers as a std::array...";
    const int size2 = 200;
    std::array<float, size2> rand_arr{};
 
    for (auto &a : rand_arr) {
        // generate random numbers between -5.0 and 4.99
        a = float(std::rand() % 1000 - 500) / 100.f;
    }
 
    std::array<float, size2> float_arr = sorting::gnomeSort(rand_arr);
    assert(std::is_sorted(std::begin(float_arr), std::end(float_arr)));
    std::cout << " Passed\n";
    // for (int i = 0; i < size; i++) std::cout << double_arr[i] << ", ";
    std::cout << std::endl;
}

Here is the call graph for this function: