Bogosort.cpp

gistfile1.cpp

template < typename container_t >

void BogoSort( container_t & data )
{
    using std::begin;
    using std::end;
    
    std::random_device rd;
    std::mt19937       ung( rd() );
    
    while( !std::is_sorted(begin(data), end(data)) )
    {
        std::shuffle(begin(data), end(data), ung);
    }
}

// suggestions from reddit:
template < typename container_t>
void BogoSort( container_t & data )
{
    while( !std::is_sorted(std::begin(data),std::end(data)) )
    {
        std::shuffle(std::begin(data),std::end(data));
    }
}

The fun question is what is the algorithmic complexity of "BogoSort".. Thinking about it there are n! combinations in array of n elements. If all the elements are distinct, then only one combination is valid. So we expect an effort of n! to find it.. clearly not the best algorithm ;-) Ah.. and you may want to write it in a generic-stl way so instead of passing a container to the function you pass iterators.

@nightlifelover The algorithmic complexity of Bogosort is technically O(∞) because the algorithm is not guaranteed to end. The average time is of course on the order O(n!) though.

When specifying algorithmic complexity, you need to indicate best-case, average-case, or worst-case. For this algorithm, best case is O(1), average case is O(n!), and worst case is O(∞). Since the best/worst cases are triggered by random chance and not bad data, average case is the standard method of looking at it.

The best case is still O(n), since it takes linear time to check whether the input is sorted.

Now make it a stable sort.. 8)