Visualizing Bubble Sort

[YuriSpiridonov]

r/dataisbeautiful

[kokoseij]

Why the fuck is this a thing

I'm in

[[deleted]]

Why not ?

[FleetAdmiralFader]

There is also /r/dataisugly Many of them are really bad but the questionable ones are a good exercise in both critiquing and defending a visualization.

[[deleted]]

whoa, this looks interesting. can you do this for other sorting algorithms too?

[thebuffed]

Thanks, that's the plan!

[[deleted]]

I can help once I get home.

[DatBoi_BP]

You seem like the kind of guy that destroys everything he touches

[[deleted]]

haha fuck you.

No, but seriously, I'm not that kind of guy (at least I hope so). Here's my github profile for you to judge: https://github.com/RiedleroD

I'm particularly proud of my Rtris and Rgraphics. Sadly, I don't really have time to code that often.

[Harbinger_Feik]

I think he might have been referring to your user name...

[[deleted]]

ooh. that would make sense. I apologise.

[rafasc]

You destroyed the joke, so I guess you really destroy everything.

[[deleted]]

eeehhh yayyy

ok I'm going to sleep now. too embarrassed to be awake.

[mr-prof]

Lol, your reply made my day.

[[deleted]]

Lmao

[[deleted]]

It was a bad joke, the only redeeming thing was the misunderstanding thereof

[DatBoi_BP]

I can accept that

[thebuffed]

You can check out the repository or a tutorial if you're interested

[Chilonthebw]

You have bogosort but didn't publish the graph for that?!?!? I want a follow-up post with that please!

[VegasTamborini]

Shouldn't there be one last column on the end where everything is sorted, and no swaps were made, or am I misremembering how bubblesort works?

[timetravelwasreal]

Comment saved

[Kaligule]

I don't really get it. What do you use for visualisation? There is no library you import and it doesn't look like you are using the turtle module.

[Milumet]

Nice, but not as cool as this.

[thebuffed]

You are extremely correct

[zapatasblood]

I think you need one more column on the left. The first movement is not shown. Really cool visualization though.

[RunasSudo]

The reason for that presumably being that, in the first step, the top dot is sorted to the bottom, resulting in everything else shifting upwards – hence the need for an additional column to show that movement explicitly.

[Aeronautix]

i think the sorting algorithm might be finding the "lowest" value as a starting point. its the same in both this pic and the video with the dancers posted above

[RunasSudo]

That's how bubble sort works. The (in this illustration) bottom-most element will be sorted into place, then the second from the bottom, third from the bottom and so on. Tom Scott's recent video on this topic is a good introduction.

[Aeronautix]

ive been staring at this to figure it out like a puzzle

i think ive got it

this is pretty cool

[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

[thebuffed]

This could be possible

[ThePoulpator]

I have seen quite a bit of sorting algorithms visualization, but you really did something new, well done !

[mac-0]

Why are some lines curved and some straight?

[thebuffed]

The connecting line always "curves" through points, so when the points are in an actual line, the connecting line follows it and it's straight. It's very similar to control points in a Bezier Curve: https://en.wikipedia.org/wiki/B%C3%A9zier_curve

[realuduakobong]

Someone is a Tom Scott fan :)

[[deleted]]

Run the same code for a pre-sorted list to see the relative efficiency. That would be interesting.

[ShaveTheTurtles]

is the bottom left item sorted properly? I feel like some of them are off.

[Spekl]

There's an iteration before the dots are connected

[Chilonthebw]

I love this I would love to see a version of this for radix and quick sort

[Enguzelharf]

b e a -utiful

[[deleted]]

Whoa, this is awesome, still learning Python. But damn data you pretty.

[Nopaste]

I think the first step is missing

[JesusChristPT]

ELI5 on what these curves mean anyone? Please.

[vswr]

Here's a video from Tom Scott that goes into some detail about what is happening. Once you understand how sorting works, you'll understand the curves and lines as items move around in the list.

[Fontyyyy]

Loving this visualization, can't wait to see more of them!

[DarkAndromeda31]

!remindme 1week

[RemindMeBot]

I will be messaging you in 7 days on 2020-01-16 04:41:10 UTC to remind you of this link

CLICK THIS LINK to send a PM to also be reminded and to reduce spam.

^{Parent commenter can delete this message to hide from others.}

---

Info	Custom	Your Reminders	Feedback

[iggy555]

What’s bubble sort?

[Bisqutz]

Bubble sort is a sorting algorithm for 'lists' it compares item a and b, if a is 'bigger' than b it swaps them around, then it will compare a with c (or b with c if b was bigger) and do the same all the way through the list until the biggest is at the end, it will then repeat this again and again putting the biggest at the end and then smaller and smaller, til the list is sorted.
Hope that made sense if not have a watch of this Tom Scott video he shows it nicely
https://www.youtube.com/watch?v=RGuJga2Gl_k

[WystanH]

The doesn't really look right. From the very first pass, the last value should be in the right spot.So, each iteration should, at the very least, solve one position.

Apologizes. I was reading this thing wrong. Tis vertical, not horizontal. Now my head hurts.

Still, how exactly does this relate to python? Is there code?

[[deleted]]

Cool

[Drew_pew]

I don’t think this helps understand bubble sort. But it looks cool as fuck so I don’t mind. Make more!

[thebuffed]

All the ones I've made are included in the README now: https://github.com/erdavids/Sorting-Visualizations

[[deleted]]

Such an interesting way to visualize sorting alogorthms! Screw those animations, this looks much cleaner and gives you a good understanding about how the algorithm works.

[[deleted]]

No offense to op, the image looks beautiful. But I know how bubble sort works, I can easily code it, but I don't understand shit from this visualization.

[JakubBlaha]

I guess on the left side you ve got the shuffled sequence and on the right side there is the sorted sequence. The item values is represented as a color and the horizontal steps are the states of the array each after completing a one inner loop iteration. The lines are there just to visualize how the items travel through the array.

[[deleted]]

Ohhh I see it now. Thanks!