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

 sorting
 Sorting algorithms.
 

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 }
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  }
108  std::cout << std::endl;
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] << ", ";
124  std::cout << std::endl;
125 }
test
static void test()
Definition: gnome_sort.cpp:85
std::is_sorted
T is_sorted(T... args)
std::cout
std::array
STL class.
sorting::gnomeSort
void gnomeSort(T *arr, int size)
Definition: gnome_sort.cpp:34
std::rand
T rand(T... args)
std::endl
T endl(T... args)
std::begin
T begin(T... args)
std::end
T end(T... args)
std::array::data
T data(T... args)