Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
bogo_sort.cpp File Reference

Implementation of Bogosort algorithm More...

#include <iostream>
#include <algorithm>
#include <array>
#include <cassert>
Include dependency graph for bogo_sort.cpp:

Namespaces

 sorting
 Sorting algorithms.
 

Functions

template<typename T , size_t N>
std::array< T, N > sorting::shuffle (std::array< T, N > arr)
 
template<typename T , size_t N>
std::array< T, N > sorting::randomized_bogosort (std::array< T, N > arr)
 
template<typename T , size_t N>
void show_array (const std::array< T, N > &arr)
 
void test ()
 
int main ()
 

Detailed Description

Implementation of Bogosort algorithm

In computer science, bogosort (also known as permutation sort, stupid sort, slowsort, shotgun sort, random sort, monkey sort, bobosort or shuffle sort) is a highly inefficient sorting algorithm based on the generate and test paradigm. Two versions of this algorithm exist: a deterministic version that enumerates all permutations until it hits a sorted one, and a randomized version that randomly permutes its input.Randomized version is implemented here.

Algorithm

Shuffle the array untill array is sorted.

Author
Deep Raval

Function Documentation

◆ main()

int main ( void  )

Driver Code

104  {
105  // Testing
106  test();
107  // Example Usage
108  std::array <int, 5> arr = {3, 7, 10, 4, 1}; // Defining array which we want to sort
109  std::cout << "Original Array : ";
110  show_array(arr);
111  arr = sorting::randomized_bogosort(arr); // Callling bogo sort on it
112  std::cout << "Sorted Array : ";
113  show_array(arr); // Printing sorted array
114  return 0;
115 }
Here is the call graph for this function:

◆ show_array()

template<typename T , size_t N>
void show_array ( const std::array< T, N > &  arr)

Function to display array on screen

Template Parameters
Ttypename of the array
Nlength of array
Parameters
arrarray to display
68  {
69  for (int x : arr) {
70  std::cout << x << ' ';
71  }
72  std::cout << '\n';
73 }

◆ test()

void test ( )

Function to test above algorithm

78  {
79  // Test 1
81  for (int &x : arr1) {
82  x = std::rand() % 100;
83  }
84  std::cout << "Original Array : ";
85  show_array(arr1);
86  arr1 = sorting::randomized_bogosort(arr1);
87  std::cout << "Sorted Array : ";
88  show_array(arr1);
89  assert(std::is_sorted(arr1.begin(), arr1.end()));
90  // Test 2
92  for (int &x : arr2) {
93  x = std::rand() % 100;
94  }
95  std::cout << "Original Array : ";
96  show_array(arr2);
97  arr2 = sorting::randomized_bogosort(arr2);
98  std::cout << "Sorted Array : ";
99  show_array(arr2);
100  assert(std::is_sorted(arr2.begin(), arr2.end()));
101 }
Here is the call graph for this function:
show_array
void show_array(const std::array< T, N > &arr)
Definition: bogo_sort.cpp:68
std::is_sorted
T is_sorted(T... args)
std::cout
test
void test()
Definition: bogo_sort.cpp:78
std::array
STL class.
std::rand
T rand(T... args)
sorting::randomized_bogosort
std::array< T, N > randomized_bogosort(std::array< T, N > arr)
Definition: bogo_sort.cpp:51