Bogosort and Fisher-Yates Shuffling


Each week /r/DailyProgrammer posts three programming challenges of varying difficulty. The challenge on Monday was to write a bogosort.

Bogosort is an especially ineffective sorting algorithm that is based on the generate-and-test (or trial-and-error) paradigm. When you bogosort a set, you generate a random permutation of the set until the set is in the order you want.

So, if you were to bogosort a deck of cards, you would:

(1) Check if the deck is in order.

(2) If the deck is in order, then you’re done.

(3) If the deck is not in order, then shuffle the deck.

(4) Go to (1).

You can see how this is very inefficient. It could be a very long time before you happen to shuffle a deck of cards into the right order.

But, in summary, bogosort is very simple. While the set is not in order, shuffle the set.

The interesting thing…

View original post 122 mots de plus


Laisser un commentaire

Choisissez une méthode de connexion pour poster votre commentaire:


Vous commentez à l'aide de votre compte Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )


Connexion à %s