68
Jan 08 '20
whoa, this looks interesting. can you do this for other sorting algorithms too?
64
u/thebuffed Jan 08 '20
Thanks, that's the plan!
21
Jan 08 '20
I can help once I get home.
70
u/DatBoi_BP Jan 08 '20
You seem like the kind of guy that destroys everything he touches
26
Jan 08 '20
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.
69
u/Harbinger_Feik Jan 08 '20
I think he might have been referring to your user name...
44
Jan 08 '20
ooh. that would make sense. I apologise.
84
u/rafasc Jan 08 '20
You destroyed the joke, so I guess you really destroy everything.
38
3
-4
20
3
u/mac-0 Jan 08 '20
Why are some lines curved and some straight?
4
u/thebuffed Jan 08 '20 edited Jan 08 '20
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
119
u/YuriSpiridonov Jan 08 '20
29
u/kokoseij Jan 08 '20
Why the fuck is this a thing
I'm in
28
1
u/FleetAdmiralFader Jan 09 '20
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.
16
u/zapatasblood Jan 08 '20
I think you need one more column on the left. The first movement is not shown. Really cool visualization though.
0
Jan 08 '20
[deleted]
2
u/RunasSudo Jan 09 '20
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.
1
u/Aeronautix Jan 09 '20
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
1
u/RunasSudo Jan 09 '20
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.
1
u/Aeronautix Jan 09 '20
ive been staring at this to figure it out like a puzzle
i think ive got it
this is pretty cool
5
u/ThePoulpator Jan 08 '20
I have seen quite a bit of sorting algorithms visualization, but you really did something new, well done !
2
2
Jan 08 '20
Run the same code for a pre-sorted list to see the relative efficiency. That would be interesting.
2
u/ShaveTheTurtles Jan 08 '20
is the bottom left item sorted properly? I feel like some of them are off.
1
2
1
1
1
u/JesusChristPT Jan 08 '20
ELI5 on what these curves mean anyone? Please.
3
u/vswr [var for var in vars] Jan 08 '20
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.
1
1
u/DarkAndromeda31 Jan 09 '20
!remindme 1week
1
u/RemindMeBot Jan 09 '20
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
1
u/iggy555 Jan 09 '20
What’s bubble sort?
2
u/Bisqutz Jan 09 '20
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
1
u/WystanH Jan 09 '20 edited Jan 09 '20
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?
1
1
u/Drew_pew Jan 15 '20
I don’t think this helps understand bubble sort. But it looks cool as fuck so I don’t mind. Make more!
1
Jan 08 '20
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.
21
Jan 08 '20
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.
2
u/JakubBlaha Jan 08 '20
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.
2
0
11
Jan 08 '20
[removed] — view removed comment
2
4
u/NumerousInMyUterus Jan 08 '20
Whats even the runtime of BOGO? Wouldnt that be something like n! ?
4
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
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"
3
Jan 08 '20
[removed] — view removed comment
2
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
1
Feb 09 '20
[removed] — view removed comment
2
u/thebuffed Feb 09 '20
All the ones I've made are included in the README now: https://github.com/erdavids/Sorting-Visualizations
48
u/thebuffed Jan 08 '20 edited Jan 10 '20
You can check out the repository or a tutorial if you're interested