bogo_sort.cpp File Reference

Implementation of Bogosort algorithm More...

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

Include dependency graph for bogo_sort.cpp:

Go to the source code of this file.

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

Definition in file bogo_sort.cpp.

Function Documentation

main()

int main

(

void

)

Driver Code

Definition at line 107 of file bogo_sort.cpp.

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

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

Definition at line 71 of file bogo_sort.cpp.

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

test()

void test

(

)

Function to test above algorithm

Definition at line 81 of file bogo_sort.cpp.

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