Bogosort and Fisher-Yates Shuffling

jdanray

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:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. 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 )

Photo Google+

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

Connexion à %s