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:

Go to the source code of this file.

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)\).

Definition in file gnome_sort.cpp.

Function Documentation

main()

int main

(

void

)

Our main function with example of sort method.

Definition at line 130 of file gnome_sort.cpp.

           {
    test();
    return 0;
}

test()

static void test ( )

static

Test function

Definition at line 85 of file gnome_sort.cpp.

                   {
    // 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;
}