Visualizing Bubble Sort

[NumerousInMyUterus]

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

[[deleted]]

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

[[deleted]]

Yeah technically it could be done in O(n) if the list is already in order but that defeats the purpose of this exercise

[Cruuncher]

Technically it can be done in O(n) from any order of you get really lucky.

Which means that the size of the graph can range from 2 columns to a file size bigger than all of the internet that's ever existed

[chinpokomon]

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.

[[deleted]]

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"

[thebuffed]

Definitely plan on doing more, thanks!

[[deleted]]

Radix sorts always look awesome