Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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.

130 {
131 test();
132 return 0;
133}
static void test()
Definition gnome_sort.cpp:85
Here is the call graph for this function:

◆ test()

static void test ( )
static

Test function

85 {
86 // Example 1. Creating array of int,
87 std::cout << "Test 1 - as a C-array...";
88 const int size = 6;
89 std::array<int, size> arr = {-22, 100, 150, 35, -10, 99};
91 size); // pass array data as a C-style array pointer
92 assert(std::is_sorted(std::begin(arr), std::end(arr)));
93 std::cout << " Passed\n";
94 for (int i = 0; i < size; i++) {
95 std::cout << arr[i] << ", ";
96 }
98
99 // Example 2. Creating array of doubles.
100 std::cout << "\nTest 2 - as a std::array...";
101 std::array<double, size> double_arr = {-100.2, 10.2, 20.0, 9.0, 7.5, 7.2};
102 std::array<double, size> sorted_arr = sorting::gnomeSort(double_arr);
103 assert(std::is_sorted(std::begin(sorted_arr), std::end(sorted_arr)));
104 std::cout << " Passed\n";
105 for (int i = 0; i < size; i++) {
106 std::cout << double_arr[i] << ", ";
107 }
109
110 // Example 3. Creating random array of float.
111 std::cout << "\nTest 3 - 200 random numbers as a std::array...";
112 const int size2 = 200;
113 std::array<float, size2> rand_arr{};
114
115 for (auto &a : rand_arr) {
116 // generate random numbers between -5.0 and 4.99
117 a = float(std::rand() % 1000 - 500) / 100.f;
118 }
119
120 std::array<float, size2> float_arr = sorting::gnomeSort(rand_arr);
121 assert(std::is_sorted(std::begin(float_arr), std::end(float_arr)));
122 std::cout << " Passed\n";
123 // for (int i = 0; i < size; i++) std::cout << double_arr[i] << ", ";
125}
T begin(T... args)
T data(T... args)
T end(T... args)
T endl(T... args)
T is_sorted(T... args)
void gnomeSort(T *arr, int size)
Definition gnome_sort.cpp:34
T rand(T... args)
Here is the call graph for this function: