ฝัง
- เผยแพร่เมื่อ 9 มิ.ย. 2019
- Visit our community Discord: / discord
This bar graph visualization features 54 different sorting algorithms sorting inputs that either were 90% sorted or had at least one number out of order.
*NOTE: Some algorithms with pathological inputs are skipped partway in this video to save time.
Check out the NEW home for ArrayV here: github.com/gaming32/ArrayV-v4.0 - วิทยาศาสตร์และเทคโนโลยี
Join our community Discord! discord.com/invite/2xGkKC2
I love how confused the algorithms are like "wtf is this some kind of joke" and they proceed to overdo it.
HEAP SORTS
They *Broke* It And Fixed It
Merge sort
Pigeonhole and gravity are still like: *??? Either way, ill just do my job*
And they do it fast either way without breaking it
Pancake sort
"The data is almost sorted."
Radix sorts: "Who cares?"
7:47 - Still the best at wasting your time, ears, disk throughput, CPU resources and sanity
Radix sort is incredibly fast at least with random input
@@marcscattolin1554
I just checked how he actually works, and yeah, seems like you're right.
Radix is like counting sort, but can use less memory for very high numbers.
At least it’s funny to watch lol
@Flippy Flip Tru although not in place radix sort is fast
its fast when you're confident that the list is random and large, if not then dont use radix lol
Wow, never seen such a dramatic difference between quicksort and stable quicksort.
Stable hates it to the point it got that slowed down
1:21 "Stable Quick Sort"
Well, he didn't act like it. In fact, the poor guy seemed rather unstable.
stability refers to the order of the elements of the same value.
Take a look at the timer, it still ended up quicker than just about every other sort. The video just played that part really, really slowly for some reason.
3 comments and none of them got the joke
@@septicstache9625 OP doesn't understand. It is quite stable, even if it appears chaotic and unstable. I know how it works I program.
@@brandonn6099 I'm pretty sure that OP was talking about the algorithm like it was a person
Counting sort: Hmm, yes, data.
Counting sort 1ms later: Swoosh, I've sorted it.
Wait, what? How?
Pigeonhole sort 0.5ms later: Swooshing from this direction is faster.
In-Place Radix LSD Sort, Base 16: *Hacking System*
@@pabloibanez8210 lol
@@pabloibanez8210 Radix In-Place 16: *hack and have a brain aneurysm*
Counting sort does it by counting the lsd from ones tensión hundreds etc
24:21: almost sorted
24:22: OH NO RANDOM
23:00 23:01
9:28 Estimated Real Time: 8,192.709ms
UM
Maybe thats why it's called time sort LOL
@@MortalMercury yeah. But what exactly is it DOING?
@@TekExplorer Idk, it was a joke
@@MortalMercury it didn't work because it's true. I just wonder what it's actually doing to be called time sort or to take so long such that it gets named time sort.
Silly and Slow Sort both got 17000 something milliseconds.
counting and pigeonhole sort: YOU DARE APPROACH ME? *sorts whole thing in half a millisecond*
Strangest asmr on youtube.
Radix LSD sort: imagine a different reality where this array was sorted
Viewer: But... It's the same. You traveled through dimensions to one where it was almost exactly the same.
Radix LSD sort: e x a c t l y
I'm so used to merge sort going "whoop whoop" and now with the almost sorted inputs it just sounds shy
next video: just 1 item out off place in the middle then let it sort that.
Go one further and sort an already sorted list.
Desort it
@@temmie9997 shuffle an already sorted array and then play it in reverse
In place LSD sort: Let me desort and resort it in 350 ms!
Radix LSD and Radix MSD are my favorites
Uses pancake sort as dystopian city skyline
Depending on your luck, bogo sort can either solve on its 1st attempt, its n!th attempt or anything in-between. For example, if you give bogo sort a random assortment of 9 numbers, it will take it anywhere from 1 to 9! attempts.
TechnoGuz GD Actually, its possible for bogosort to never successfully sort an array larger than size one, its just Probability 0.
@@connorhorman Depends on if it's random or permutative
Brandon N bogosort is random.
@@connorhorman There are versions where it goes through every possibility instead of randomly
@@brandonn6099 it still takes over 1000000000 comparisons to sort 20 units, no matter what
i love how the heap sorts just take a look at the almost sorted graph and just throw that all out the window
They do that even when it's already done
Yep they always make their heap no matter what the array is. It makes the time taken to sort the array exactly the same each time so the time complexity never changes
It's possible Slowsort and Badsort just have a confidence problem.
try to give it more motivation
You can do it badsort! I believe in you!
DemNoel The Internet Guy you can do it goodsort!
Badsort was actually one of the fastest sorts. It only took 5ms.
@@nathangamble125 Like the other "impractical" algorithms at the end it sorted only 256 numbers instead of 2048.
AutoCaptions: [Music]
Yeah, there's no other way of describing this sound
lmao, I love how some of these just make it worse before making it better
Bogosort: NOOO, YOU CAN'T JUST FLIP IT AND GET IT RIGHT!!!
Pancake sort: flip go brrrrrrr
18:04
Captions: [Laughter]
Ahh yes, I too laugh in kfuenmfiwunrnlcuzhnekfi
combing sort is really good at making the data almost sorted, it’s just slow finishing it off.
Combining it with a pidgeonhole sort would probably be a really fast algorithm.
I think insertion sort would be a better "partner" for it, so it won't need a second array
Pigeoncomb sort
@@francescodelellis8932 hybrid comb
I like how bad sort is actually really fast in this situation
It's situations like these that explain why I like Bubble Sort. No BS complicated algorithm to add steps when it's sometimes just not necessary.
but very slow
if you want an easy to implement algorithm that does relatively well, use insertion sort
infact many hybrid algorithms use insertion sort for small subarrays
1:22 is my brain when I try to put two things together.
25:41
Best sort yet
All hail BogoSort!
I have an indescribable hatred for the comb sort
I will never understand wtf pancake sort is doing but it's a masterpiece
Damn max heap lookin good 2:47
Me: turns on the washing machine
The washing machine: 0:55
Heap Sort: I'm not gonna hurt myself I'm just gonna start from scratch
Silly sort and pancake sort didnt even try
meanwhile, pigeonhole went ‘hold my beer’
Pigeonhole is my favorite sorting algorithm
Its Actually The Best Sorting Algorithm
@@indeepjable nope. It requires insane amounts of auxilliary memory. Even more if the array elements werent distributed evenly on a straight slope
@@Alexander-oh8ry i'm an outsider to this stuff. what exactly determines the best sorting method? i imagine it's not a linear answer but if it's possible eli5
@@Hexhammer depends heavily on the purpose and circumstances. Bubblesort is pretty bad, but very easy to implement, counting/pigeonhole sort are very quick if you have enough memory, etc. The Introsort can be considered the best, as it tries to determine which subalgorithm should be used to continue sorting. Just the ones with negative names, plus stoogesort and gnome sort (basically a dumb insertion sort) and bogosort and bozosort are literally useless
When I saw Gravity Sort I was like "damn, that looks really cool"
Then I saw In Place Radix LSD Sort, Base 16
Radix MSD Sort Base 8 sounds like a sick beat
From This I think I'll use bogo sort
It would've taken nearly forever if done with more numbers...
@@quinn7894 it doesn't matter how many numbers there are
bogo is definitively the worst
it just randomizes until sorted
r/woosh
@@weeaboo869 worstsort is worse
This input: Skip my sorted elements
Heap sorts & Bogo sorts: No you
Stooge Sort: Let’s party and go anywhere but the workplace.
Bogo Sort: Aah! I know where it belongs! Now where do I put it?
HOLY SHIT BOGO SORT ACTUALLY DID IT
WE ARE SO PROUD
3:11 Min heap is DEFINITELY not an option.
Selection sort: nice
i wish we have algorithms that detect if its reverse, partially sorted, noise
We have, but it is simply better to start sorting immediately.
Thats timsort
A variant of quicksort that may have been seen in this video and is called introsort, does this. Ironically, quicksort performs at its worst when the array is almost or already sorted and the pivot choice is always a maximum or a minimum.
What this variant does is it only runs for log n recursions on a particular array before it calls heapsort to sort the remaining elements. For example, if the array were sorted in reverse and the rightmost element was always the pivot, the array would be sorted with heapsort after log n iterations.
Here's a suggestion for one of these videos: a list that is almost fully sorted except that there are half a dozen or so misplaced items on the end. Like you had a sorted list but then added some more items later without putting them in the right place to begin with.
I hate to be rude, but that's basically what this video is.
@@Musicombo
Well, except the out of order items are scattered through the list at the start. I'm thinking more like "1 2 3 4 5 6 7 8 ... 2046 2047 2048 13 42 17"; as if the list had been sorted and then three more items were appended. I'm looking at the code but it's been yonks since I did any Java.
@@nickfarmer2452 I mean, I see, but it would be similar in many ways to this video. I'll deliberate.
@@Musicombo I suppose it would be a "worse case" scenario for the insert/select parts of the code? I mean you'd only be scrambling the end. I guess the question is "How does this sorting handle a partially sorted algorithm?" Then again.. that is what the sorts approach at the end.
I think if you were able to overlay a time based graph of the "swaps/ms"(basically the time it takes to get one data point from its initial position to another) it would be cool to see the change in performance over time. Some of them feel like they slow down A LOT towards the end.
BTW I should have watched these before commenting last LOL. I love the metrics.
Reverse bad sort's search direction and add a fence to sorted bounds and you have a stupid fast list flipper, most definitely.
the bogo sort is the fastest if you’re very lucky
7:13 DAT SPEED
its my fav pigeonholes algorithm 7:13
Dude - I have an idea for a sorting algorithm, is there an interface that I can code to and give you the code for it? It's a hybrid sort: SmoothShell. Shell sort, but each 'shell' is sorted using smoothsort. As shell sort progresses, the shells are kinda/sorta in a rough order from the coarser shells, so smooth sort ought o be able to deal with them well.
Just write it out in Java and I'll see what I can do!
Paul Murray Why don‘t you try something similar with Quicksort and Radix MSD?
If you need a name, I'd suggest quail sort. If you're asking why, just search up "quail bird call."
"Bad Sort" wasn't all that bad this time around. It outdid a good number of the more common sorts.
Bad sort did 256 numbers, some of the others were doing 2048
Bogo Only Did 7 Comparisons And Nothing Else
@@indeepjable bogo only did 8 numbers
*Put It On Max*
radix sorts: I DONT CARE IF IT IS ALMOST SORTED, MOVE ALL OF THEM!
"*you sure its stable bro?*"
"*yeah dont worry*"
at least the gnome sorts knew what they were doing and didn't freak out like stable quicksort
2:48 is so satisfying
time: i'm the most useless sort!
gravity:...
Is there a benchmark for algorithms which are very quick in approximately sorting random numbers? Where "approximately" means that after sorting, each element is "close to" its optimal location. For some tasks approximate sorting should be enough. Maybe such an algorithm could be faster than one which sorts perfectly. (Comb sort indeed has such approximate results as intermediate results, but it is not very fast.)
10:24
This entire sort just looks like screenshots of a sorting algorithm fading from one to the next.
13:54
This entire sort was painful to watch.
god i fucking love bogo soRt
When bad sort actually does good
base 16 was wild
Pancake sort: R E V E R S E A R R A Y
I just wanna know how does the In-place Radix LSD sort base 16 works. I wish I could know how all of these sorting algorithms work.
And even worse, why do some of the most complex ones dont even compare or swap at all. How do they figure out where goes where?
The channel Discord is buzzing with people who would love to teach you how sorting works!!
We're all here for LSD Base 16 sort and we know it.
I came here for pigeon hole sort
I’m a sucker for gravity sort
Looking for the iterative merge kind of stuff
Have i mentioned how much i fucking love quick-sort and comb-sort? Both for the aesthetic, tho quick-sort gets extra points for being efficient as fuck.
2:47 i was flabbergasted
With any of these sorting vids, i’m always confused about the time like some sorts seems slower than others but the Estimated real time is way faster what is this?
The delay varies to allow us to see what the algorithm is doing, you can see the delay between steps above the estimated real time.
TehSoulja yeah okay that makes perfect sense
It's because the algorithms can't be all shown with the same scale of speed
0:00 Run All: Done
Sorting algorithms visualized except it's in real time
Pancake sort... buddy... what are you doing?
Edit: just got to silly sort... half a billion comparisons for 256 numbers???
Just normal Silly Sort things.
yes more sorting :Y
Juice gg on first
what on earth does time sort do?
Radix base 10 walked so Radix base 16 could run
2:38
Plays bumblebee instead
What are those sorting algorythms used for?
certain types of modern electronic music
@@TheVergile for real? for electronic music? because before i get a r/woooosh from anybody, i really don't know this.
@@timo.eppler nah, thats a joke.
as the name says they sort data. they basically take in a list of unsorted data points and try to produce a list of ordered data points. its not a complicated task, but depending on the type of data and hardware you have different approaches result in very different performance.
hence there is a ton of different sorting methods for different applications.
even the windows "organize file by "Time/data/name" use some sort algorythm of those, they all can sort the files only difference is performance/time, some are just used for programming lessons to teach how to bad code something tho like bogosort.
@@timo.eppler check out bitonic beats it's lit
How is patience sort worse than pure merge? It should be faster since there would be larger piles due to the list being already almost sorted
The fastest sort remains pigeon hole sort and I don’t know why. Could someone tell me why?
the equivalent of using quantum mechanics to answer 2+2
Gaming in the Future:
Radix LSD sort be like "Ah yes, this array seems mostly sorted. Time to ruin it"
LSD sorts start at 7:18
So bad sort is better than merge sort?
nin10dorox bad sort had less numbers to sort
@@ReaSeBy Still, "bad sort" is a lot less bad than the other non-serious sorting algorithms, and fairly close to some of the serious ones.
What are the purpose of shorts tho ?
Gnomed
when a quarter of the vid is pancake sort
Ruler sort:
I take a ruler, make the diagonal and whistle. It is pretty slow, Estimated Real Time: 5 000 ms
Why am I watching algorithm videos at 2:00 AM help me
Why does gravity take so long
Gnomes sort
I feel like comb sort is the least satisfying sorting algorithm to watch. It doesn't even have the "he's trying his best" appeal of bogo sort. It's just unsatisfying.
9:18 how did timesort manage to take 8 seconds just for 2048 writes to the array!?
Still waiting for the beat drop
What is this
What is the point of this
Why am I still watching it
17:08 what am i watching
Bogo sort: Nearly sorted? Wdym?
0.55 like grass
Smooth sort and Tim sort are good for almost sorted data right? I guess it
Yes, correct, but in my opinion, TimSort is a much better choice.
Bad sort very good 7 ms XD totaly unsorted data it takes eternity to sort with that
@@Musicombo How can you defend that statement? The question was about ALMOST SORTED data. Smooth sort has been know for decades to be the best for ALMOST SORTED data. From your own video Smooth sort is FIVE times faster than TimSort on ALMOST SORTED data. TimSort is a better choice if you do not know in advance that the data are ALMOST SORTED, as it figures that out and adjusts. But if you already know ahead of time, Tim sort cannot compete at all with Smooth sort. So with ALMOST SORTED data TimSort is NOT a better choice... it's a dumb choice.
...Excuse me? I would appreciate it if you would talk to me without slinging around insults.
Smoothsort is constantly slower than Timsort on average. It's less cache-friendly and much more complex. So no, Timsort is *not* a dumb choice... It's the smarter choice.
@@Musicombo And yet your video proves otherwise.
GUYS BOGO SORT DID IT FIRST TRY
25:40
thanks youtube
Aw poor max heap sort 2:48