Slow Sort
ฝัง
- เผยแพร่เมื่อ 20 ก.ย. 2024
- Visualization and "audibilization" of the Slow Sort algorithm.
Sorts a random shuffle of the integers [1,50] using slow sort. It uses the implementation from de.wikipedia.or... . Slow sort is very very slow, but not as slow as Bogo Sort!
More information on the "Sound of Sorting" at panthema.net/20...
slow sort is just merge sort with the severe paranoia that the elements have moved themselves while it wasn't looking.
+drew b. Oh my god I'm crying. It even *sounds* paranoid and stressed in the video.
"Okay, okay, after nearly fifty thousand comparisons, the list is *finally* sorted.
-I _think_ so, at least... I should check it one more time, just to be sure!
...And a second time for good measure.
...And a third time for luck.
And another because _oh god please stay sorted fuck fuck fuck-"_
lol
lol
lol
Fun fact: This algorithm was created to be the least efficient way possible to sort an array without deliberately making things any worse. The implementation was proposed as a counter to the "divide and conquer" strategy that Mergesort works on, and the author called it "multiply and surrender". It was the subject of his Master's Thesis.
scitechian Multiply and Surrender 😂😂😂😂
Tell me he got an A++++
welp I guess whoever made it got screwed over by the bogo sort, where you literally just randomly organize everything and hope they're in the right place
@@xinlidai1642 "without deliberately making things any worse"
multiply and surrender hahahahahahahahaha
@@xinlidai1642 You're forgetting about bogobogo sort. Bogo sort is only O(n x n!). In bogobogo sort, you use bogo sort to sort every sub-array of the list.
When they pay you per hour
lol
lol
Luck no that's when you use BOGO sort 😂
joseph jackson ew you didnt say lol
lol
You took a perfectly good computer and gave it anxiety, good job.
This is the best way to describe it
You know you've been programming too long when you find a sorting algorithm to be hilarious.
+Ryan N
Exactly! I'm cracking up harder over a sorting algorithm than something that was actually intended to be funny.
LMFAOOOO
Counting sort is in the corner like: "One... two... and done!"
Ryan N I'm not even a programmer and I find this hilarious lol
Ryan N I've never programmed anything and I find this funny.
I strongly empathize with this algorithm.
Arthur Hill first reply with 58 likes
Agree, this one is me in real life
woah thats a lotta default pfps
Sounds like some kind of experimental jazz. I love it.
Sounds like Mario music at 0:09
1:27 Time Forward! starts here))
sounds like nothing at 3:05 ecks dee
I think it's supposed to be the flight of the bumblebee
YA LIKE JAZZ?
From the Wikipedia article: "Even the best case is worse than bubblesort" AHAHAHAHAHAA
meanwhile bogosort:
@@owenyin3316 the best case would be first try so its better than bubble sort
It is a sorting network, always the same comparisons for the same amount of items
@@groszak1 this is nowhere near true
DONT MAKE FUN OF BOGO SORT
This is how I check my answers on an important test.
Icy Pengin first reply with 32 likes 77 now
Iqbal Mala who tf cares
MamboBean it's a joke man hahaha
BananaCupcake I was replying to Iqbal Mala, not the joke
MamboBean minecraft is my favorite game
You could probably sort it faster by hand.
because you'd use like insertion sort (or radix base 4 sort if sorting a deck of cards) by hand.
Or be and idiot and use bogo sort be throwing the cards in the air than picking them up
i agree with him? ^
Jackie Brzostek it all starts with a deck of playingcards.
@@raffimolero64
Wait, you guys aren't bubblesorting a pack of card ?
In case you’re wondering, this is what’s happening:
Split the array in half.
Sort each half with slowsort (recursively).
Compare the highest element from each half.
Move the bigger one to the end of the list.
Repeat from the top, omitting the last element (the one moved into position) from the sorting.
Basically, a demented combination of merge and insertion sort.
Edit: Merge and SELECTION sort, my bad.
Seeing it explains make it sound more horrible than I imagined.
it's based on the principle of multiply and surrender
i dont get it
In other words.......
Music go big to smol
I thought slowsort made with threads where each threead waits as the value in the cell then put the value in another array
At least it can finish, bogo sort would likely take a 1000 years.
technically bogosort could be a lot faster
Yeah, bogo sort could finish on the first try.
Yes, well know, that the Best Case for Bogo Sort is O(1), but the average case is O(N!). Not to mention, that the worst case is O (infinity)
@@ilmu011 averege is O((n+1)!)
@@mattia2510 In the O-notation constants are completely irrelevant. It is only supposed to describe complexity with a growing number of range.
O (5) is the exact same as O (999999999999) is the exact same as O (1)
The complexity is constant. Usually this is marked with O (1), you can say O (2) but it doesn't add any information about the complexity.
Same with O (n+1). The N already states it's linear. The +1 doesn't give us any relevant infornation about the complexity.
I could say that a certain sorting algorithm will always take a number of steps equal to the size of the array plus 100.000.000.
You could say that the complexity is O (N + 100.000.000), but that doesn't change the fact that the complexity is still linear, so normally you would still only say O (n).
Musically, this is the best one!
diegofloor first reply with 70 likes
diegofloor he, I like the music for BOGO more
bogosort
I tried to mimic the temperment of this, and got what roughly translates to 22 tones per 1.5 octave. The fact that an algorithm with random numbers can generate full fledged microtonal music is insane.
The formula they use for the frequency is 120+1200*x², where x is from 0 to 1. In this case it's x being [1, 50]/50, which is from 0.02 to 1.
@@groszak1 ah thanks :)
I want a musical sorting algorithm.
@@GabrielsEpicLifeofGoals I'm writing a VST inspired by these videos, what exactly did you have in mind?
heading to improvise in this tuning years layer
It appears to tickle the integers before moving them.
404_name_missing en.wikipedia.org/wiki/Joke
404_name_missing woosh
404_name_missing
You failed turing test, go back to your server
This just made me laugh out loud
@404_name_missing /r/whoosh
It may be slow, but I believe in it
I'm a beginner in computer science and I couldn't even think of how I would go about programming something like this. Something this inefficient can not be accidentally programmed. This is awe inspiring.
Apparently it wasn't an accident, it was deliberately made to be seriously inefficient
@@FarmYardGamingit was
love how slow sort was deliberately programmed to sort as inefficiently as possible without including random elements as a joke.
It's even more hilarious when you know how to works. Basically it recursively sorts two approximately equal subarrays (like mergesort) then looks at their highest members and swaps them if they are in the wrong order thus ensuring that the highest element is in the right place (like selection sort). Then it runs itself recursively _once again_ on the rest of the array. The author called this strategy "multiply and surrender" as opposed to "divide and conquer".
How IT* works?
youtube put this in my music playlist...
i am proud
youtube knows their shit
Lol best music of the century
Sounds quite nice around 1:10.
Lao Tzu yes, i agree
It plays the same two 7th chords over and over, only faster everytime
I like the part from 0:31 to 1:02
Fun fact - the benefit of this algorithm over bogosort is that while bogosort has O(n!) time complexity in the worst case, it still has O(n) time complexity in the best case! The best case complexity of slowsort on the other hand is w(x^n) for any n. If that's not an achievement, I don't know what is.
I thought that the time complexity for this one is O(n^log n)
Isn’t bogosort technically O(∞) in the worst case since it could theoretically never finish?
@@DannyDog27 Bogosort is guaranteed to finish because at least one of the random permutations it creates is the sorted array (or else it's not a truly random if it's avoiding the permutation that is sorted)
@@ahnafabdullah3342 That’s a common misconception about probability. If no one permutation is guaranteed to be the correct one, there is also no guarantee that an infinite number of random permutations will contain the correct one. That’s like saying if you flip six coins there’s absolutely going to be three heads
@@DannyDog27 Probability only makes sense when you have a variable/controllable number of events. Obviously there is no guarantee that you will have 3 heads if you flip 6 coins. But as you flip more than 6 coins, the expected number of heads will rise and the probability that you got 3 or less than 3 heads will become exponentially smaller. Similarly for a list of 100 items, once 100! number of random permutations have been generated, the probability that at least one of them should have been the correctly sorted permutation will now be significantly large and will continue to increase in size, until it becomes something 99.999999%...
If you only have 100 items, but you generated 9999999! permutations (which is a lot of permutations), to say that you don't have a valid permutation by then is ridiculous. Hence it is not logical to describe the time complexity of bogo sort as O(∞). By definition an algorithm is defined to have a finite number of steps.
There is certainly some musical property in this:D
"There appears to be no signs of intelligent life anywhere."
Sounds like it's laughing at me.
It's sorting jazz :)
Damn need to watch this again, couldn't grasp a shit twas that quick.
MrPrzepior not me
If common core taught you how to sort
Fartonaut LoL
"Sort the numbers by making a ten and counting around while the merry-go-round broke down."
dude you don't know anything about common core
If a dumb education system (not necessarily Common Core IMO) were to teach a sorting algorithm it'd teach the absolute simplest variant of bubble sort (i.e. "repeatedly scan the array for out-of-order pairs and swap them until there are no more out-of-order pairs to swap").
I hate that I can relate to this algorithm on a spiritual level. If you want to know what it's like living with an anxiety disorder, all you have to do is imagine that this is how your brain works.
This one sounds the best out of all of the sorting algorithms
It sounds... classical. High and low chords.
0:01 - 0:30
0:58 - 1:25
1:43 - 1:56
This looked like Merge Sort, only 10000000000000000x slower.
we look the same
oh hey are you weee50 from discord?
weee50 It's also in-place, so you can sort giant arrays with this without worrying about memory.
You might need to wait a year until this sorts such a giant array though...
Doruk Ayhan One could just use heapsort for that. It looks here like someone attempted to design a sorting algorithm, but either added an unnecessary step or forgot to put something out of a loop or recursive method.
It's slow, but not that slow.
Me: How quick can you sort 50 objects by size?
Computer: Hmm. I can do it in 3 minutes with 40000 comparisons.
Me: WHAT DID YOU DO WITH MY COMPUTER? DID ALIENS TAKE IT?
This makes some pretty neat music
Bad for sorting, but great for making what sounds like chiptune renditions of classical music
Mario music in castle when you almost out of time
This is a damn fine classical piece.
Sounds like hell trying to play jazz or something...
it's great how you have considered a wide variety of algorithms, the silly algorithms are very educational for purposes of compare and contrast
I keep coming back to this video because of how musical it is. I love how it sounds so somber and how it gets more frantic at the end. Like others said, it sounds like a classical music. I would make a composition based on this if I knew how to!
This video is hilarious for some reason. I dunno, I can't stop laughing.
Braden Best it's paranoid the elements might've moved when it wasn't looking...
Same. I always laugh my ass off when slowsort or bogosort comes up during my daily 40-minute sorting algorithm session
For anyone asking how this sort works, here I’ll explain.
Well, to start off with, it’s like merge sort, obviously, but instead of just combining the already sorted sections, it does the one that goes in last. The it does the merge sort again sans the last one. And again. And again. And so on until it’s sorted. Basically this means it sorts the ENTIRE LIST every time it puts a singular entry where it should go.
I'm picking up what this algorithm's laying down
_smoo-oth_
A slower algorithm would to create a physics simulation with particle size representing the values and putting all of them in a jar and shaking it until they eventually sort themselves out with the largest particles on top and smallest on the bottom.
I didn't know something was slower than the bubble sort. oh damn
It's a multiply and surrender type algorithm. It was meant as a joke.
Painting Jo I mean you could make an arbitrarily slow algorithm. Just have it run a pointless algorithm as a subroutine. Stoogesort is also pretty slow.
2 words
BOGO
Sort
@@ilikeoranges4 three (two) words
Bogobogo sort
does it have OCD
No
It has paranoia
ocd would be more like swapping two integers back and forth ten times and starting over if certain completely irrelevant conditions weren't met with every swap
Well yes, it was designed to be the least efficient sorting method possible without deliberately making things worse (ergo bogo sort) and being OCD is one way to do that
- So, what kind of music do you like?
- It's complicated...
Thats real prog \m/
Slowsort has the grandeur of a masterpiece of classical music when given audio form
I love the music.
I'm glad somebody thought to make a slow sort.
"whats it doing?"
"its best"
Sounds like retro video game music. You could honestly put this in a video game and I would think “yo this shit slaps”
2:56 it took him 3 minutes to calm down
2:50
*you hear sonic drowning in the distance*
Me: what the?
It’s like fidgeting, it wants everything to be perfect, but the steps to becoming perfect also have to be perfect, and those steps have to be perfect too!!!
Very wonderful inefficient coding I have ever seen, bravo!
how did you get footage of me when walking home?
Mom: what are you doing?
Me: watching a sort play with itself
1:18 sounds like a soundtrack from those old-timey cartoons
this is the most relatable sorter I've seen
Thanks for gradually lowering the ms delay. It will take forever if ya didnt.
This is some good music, honestly
1:26 is when the funny part starts
1:48 is when it starts to get a little creepy
Slow sort is like a guy trying to get a job as a photocopier, but doing it the photocopier way, one pixel at a time.
good God if the aliens find this we are screwed
HowToBeAwesome _ "..."
"..."
"..."
"..."
"Okay but why"
You don't need to use quotations on that, aliens would basically think we're completely retarded if we presented this algorithm to them.
Reminds me of Patrick trying to fix his house up before his parents arrive.
This sounds like an actual classical music composition; I quite like it.
Elon: How was school kiddo?
X-AE-A-12:
Does the first few, good
does the second set of few, good
goes back to the first set .. r u srs?!
but LOOK MOM IT MAKES MUZIK
sometimes it can produce some pretty good chords, so i enjoyed listening to this one
this is art
Idk why these were in recommended but they're oddly satisfying to me
When youre good at your job but scared youll screw up
This is like that OCD person sorting something and has to sort each little section first before moving on.
Need to watch this again for the 67th time, because why not?
Random sort is the best, just randomize elements and wait until a1
That's called bogosort
1:03 sounds like some avant-garde Prog rock kinda music
Still faster than Bogo Sort.
Man, I didn't knew that Beethoven invented a Sorting Algorithm
Great👍
Thanks! Slow sort was my favorite!
Multiply and surrender sounds beautiful
Quicksort: A revolution
Mergesort: New beginnings
Heapsort: Interesting opportunities
Slowsort: *A f*cking mistake*
2:36 sounds like Delfino Plaza Anxiety Edition
*POV:* you constantly second-guessing yourself on a simple math problem
The perfect sorting algorithm when you're terrified of space radiation.
POV: Me triple checking my code to make sure it didn’t change by it’s self.
Sounds like music for a game where youre travelling thru a dangerous environment
This belongs in a horror movie!
And the Academy Award for Best Original Score goes to... Slow Sort!
could this algorighm be used to play an audio track at different relative play positions in audacity for example
also holy fuck this is so fucking agro awesome work
It's kind of endearing and cute in a way.
2:15 anyone else hear one of the battle songs from Crimson Skies High Road to Revenge?
*NEW MUSIC GENRE BORN RIGHT NOW*
I used to play this on my piano all the time
This one feels like some fiery electric jazz piece with some Scarlatti attached to it.
Someone saw bogo sort and said, “How can I increase the comparisons and array accesses while making it annoying to look at from a human perspective?”
When I turn the video on it’s side as if the black part is a pyramid aiming at the sky I understand the cascade of the scales so much more efficiently
Hey! Don't offend Bogo! In the optimistic situation it's the fastest!
(Don't kill me)
0:38 - Casually plays several good chords
2:39 - Just keeps going
Wait, Slow Sort doesn't have polynomial runtime? So it is even slower than Stooge Sort? Ridiculous!
Best sounding one so far