Skip to content

Instantly share code, notes, and snippets.

@jrandom
Last active August 29, 2015 14:12
Show Gist options
  • Save jrandom/b4dd0d0f8200217c44d1 to your computer and use it in GitHub Desktop.
Save jrandom/b4dd0d0f8200217c44d1 to your computer and use it in GitHub Desktop.
Bogosort.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);
}
}
@LeftofZen
Copy link

@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.

@mercere99
Copy link

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.

@miatauro-NASA
Copy link

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

@wagle
Copy link

wagle commented Dec 27, 2014

Now make it a stable sort.. 8)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment