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

3

u/[deleted] Jan 08 '20

[removed] — view removed comment

2

u/[deleted] Jan 08 '20

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

1

u/Cruuncher Jan 09 '20

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

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"

2

u/thebuffed Jan 08 '20

Definitely plan on doing more, thanks!

1

u/[deleted] Jan 08 '20

Radix sorts always look awesome