r/Python • • Jan 08 '20

Visualizing Bubble Sort

Post image
2.1k Upvotes

73 comments sorted by

View all comments

11

u/[deleted] Jan 08 '20

[removed] — view removed comment

4

u/NumerousInMyUterus Jan 08 '20

Whats even the runtime of BOGO? Wouldnt that be something like n! ?

4

u/[deleted] Jan 08 '20

On average Bogo sort is O(n*n!) but there isn't a guaranteed convergence

1

u/chinpokomon Jan 08 '20

It's pretty quick on a set of two, and I believe for a properly implemented BOGO, on a set of two, convergence would be guaranteed over an entire run. The worst you could say is that it would be an inverted sort order, but still ordered nonetheless.

1

u/[deleted] Jan 08 '20

For a very small set it'll be quick since it just tries ever permutation. There's also a randomized version where it randomly permutes the input which doesn't guarantee that it will ever finish.

An analogy of the randomized version from Wikipedia: "sort a deck of cards by throwing the deck into the air, picking the cards up at random and repeating the process until the deck is sorted"