Implementation of Bogosort algorithm More...

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

Include dependency graph for bogo_sort.cpp:

Namespaces
namespace	sorting
	for working with vectors

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

           {
    // Testing
    test();
    // Example Usage
    std::array <int, 5> arr = {3, 7, 10, 4, 1}; // Defining array which we want to sort
    std::cout << "Original Array : ";
    show_array(arr);
    arr = sorting::randomized_bogosort(arr); // Callling bogo sort on it
    std::cout << "Sorted Array : ";
    show_array(arr); // Printing sorted array
    return 0;
}

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

T	typename of the array
N	length of array

Parameters

arr	array to display

                                             {
    for (int x : arr) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}

◆ test()

void test ( )

Function to test above algorithm

            {
    // Test 1
    std::array <int, 5> arr1;
    for (int &x : arr1) {
        x = std::rand() % 100;
    }
    std::cout << "Original Array : ";
    show_array(arr1);
    arr1 = sorting::randomized_bogosort(arr1);
    std::cout << "Sorted Array : ";
    show_array(arr1);
    assert(std::is_sorted(arr1.begin(), arr1.end()));
    // Test 2
    std::array <int, 5> arr2;
    for (int &x : arr2) {
        x = std::rand() % 100;
    }
    std::cout << "Original Array : ";
    show_array(arr2);
    arr2 = sorting::randomized_bogosort(arr2);
    std::cout << "Sorted Array : ";
    show_array(arr2);
    assert(std::is_sorted(arr2.begin(), arr2.end()));
}