19:11 For anyone wondering how the Pidgeonhole sort manages to solve this so quick, the sorting algorithm is designed in a way that it's faster the more unique elements are in the set it's sorting. Since every element in this set is unique, it's able to do it almost instantly.
@@bugz000I'll explain the algorithm, btw if anyone who reads this doesn't know an array is just a list of values and an index is a position. • Find the lowest (min) and highest (max) values. • Set range as max-min+1 • Create a new empty array, it should be as long as the range. • Copy each value from the main array to the new array, but at the index of value-min. For example, if min is 1 and the value you're at is 2, it'd go to index 1 (arrays start at index 0). Min would be at index 0 (beginning). • Now array 2 is in order but may have some gaps if the main array isn't consecutive. E.g if the array doesn't have 3, index 2 (3-1) would be empty. • Go through array 2, and if the index you're at isn't empty, copy it back to the main array, starting at main array's index 0 and increasing it every time you copy something to it. Now every item in the main array is in order and there are no gaps.
@@bugz000 if i had two reds, and handed it to pidgeonhole, it’d take a hot minute cause they aren’t unique if i gave it a red and an orange, it’d sort near instantaneously. unless you want the explanation of how the sort works that’s all you’re getting
22:08 there are a million words in the english dictionary and, as someone who binges sorting algorithms from time to time, i could never possibly string enough words together to aptly describe how this makes me feel
Tried to do my best with the audio here, guys... Hopefully my computer gets fixed soon so I don't have to record on the family Mac anymore! Visit the channel Discord! discord.com/invite/2xGkKC2
Its crazy out the sort time and the visual time never line up with other sorts. Some take take visually like 20 seconds but take 15ms to finish, other visuals have like 1 min and only 10ms to finish.
are some of the slower sorting types more optimized for different situations or is there no real reason to use more than a handful of fast algorithims?
There are a number of factors like stability (which is needed if you want to, say, sort a deck of cards by both rank and suit), memory use, and whether there are different patterns (insertion sort is always super fast if (and only if) the list is already almost sorted for example, some only work if the array is a power of two large (which is why every array in the video (except bogobogosort) is a power of two large, so as many algorithms as possible can be shown), some algorithms are better able to handle if multiple items on the list are identical, etc), or simply the complexity of the code involved (anyone can code bubble sort in minutes, but something like timsort might take days if you have to do it from scratch and without documentation (ie you can't just use the standard Python library)). Memory use is a big one. You may have noticed that most of the algorithms in the fastest (32,768) tier (such as most merge sorts) make heavy use of an auxiliary array, which is an instant doubling of memory use at minimum. Quicksort is considered the fastest general purpose sort precisely because it reaches the highest tier while being more memory-efficient than most alternatives (but it's not stable). Most slower algorithms also avoid using an auxiliary array (and often use even less memory than quicksort), but are good enough on small arrays and can outperform faster algorithms if there are certain patterns in the data. Algorithms that do use an auxiliary array also tend to outperform quicksort if certain patterns are present (while still being able to match it in the worst case), and are also more likely to be stable (such as most merge sorts and some radix sorts). Some sorts are more art than anything practical. Bogosorts are designed to explore just how slow sorting algorithms can be for example.
Quick sort with left\left pointers looks and sounds a lot like impending doom, it creates better suspense and expectation than some movies they make these days...
@@Musicombo Bogosort randomize the entire list, permutation sort, test every permutation of the list until its find the sorted one. At a list [3,7,4] It would check if the list [3,7,4] is sorted, it would fit its not, then it would check if the list [3,4,7] is sorted and would discover it is sorted, and stops there. At bogo sort the next permutation to be checked wouldn't necessarily be [3,4,7] and also at bogosort there is a chance to check the same permutation more than once. At permutation sort if the correct permutation of the list is the last one that will be checked it will need to check ALL permutations first, when talking about bogosort there is a chance the permutation is checked earlier.
Okay so in this video its the entire continental mainland of the WORLD that we are instantly measuring at the start of each sort, using Borg technology to scan the earths surface, obviously. THEN this sorts out every tiny little cove, spit, beach, fjord, inlet, and all until its a straight line you can put an exact number on 🤣🤣🤣
From en.wikipedia.org/wiki/Bogosort#Related_algorithms, "It works by recursively calling itself with smaller and smaller copies of the beginning of the list to see if they are sorted. The base case is a single element, which is always sorted. For other cases, it compares the last element to the maximum element from the previous elements in the list. If the last element is greater or equal, it checks if the order of the copy matches the previous version, and if so returns. Otherwise, it reshuffles the current copy of the list and restarts its recursive check."
tournament sort and patience sort are my favorite because they just go from chaos to instantly triangle edit: also unbalanced tree sort edit 2: and counting sort and pigeonhole sort wow i am forgetting a lot edit 3: no bogo sort doesnt count edit 4: flash sort is also cool edit 5: i guess shatter sort? not really
Nope. Odd even cannot be combined with bubble sort as it is already a bubble sort variation. That's like trying to combine shell sort with insertion sort.
And the best part.. it's not even in-place. Just a little more memory conserving. I think it should be considered an impractical sort because for a way better performance you can just use sample sort or flashsort
I've answered this question multiple times before, but that would lead to a very uninteresting video considering Bogo Bogo Sort can only be fed up to 6 numbers before the amount of time it takes to finish becomes unreasonable.
@@Musicombo maybe you can sort theeeeee categories of sorts, from fast to slow, andn only compete the fast sorts with the fast, middle withh t he middle, and slow withthe slow. idk about bogobogo tho
bogosort is the only one that can potentially, with only one swap, solve an array that is in an undetermined order
keyword: potentially
@@paramitahalder6943 _thats the whole reason why he said "potentially"_
You could add a check function to see if its sorted at the beginning of every algorithm
@@0x19 @Pablo Rg Bogosort already does that. The best case, O(n) is for sorted arrays.
@@californium-2526 My comment was a reply to a later deleted comment that didnt understand why "potentially" was used
Well yeah, cuz it's random. But that's EXTREMELY unlikely.
Looks like this channel is all sorted out.
Lmao xD
Padum tss
You are now my favorite person
Uh oh
@@felixfernandez6056 do you have other favorite humanoids
19:11
For anyone wondering how the Pidgeonhole sort manages to solve this so quick, the sorting algorithm is designed in a way that it's faster the more unique elements are in the set it's sorting. Since every element in this set is unique, it's able to do it almost instantly.
you answered nothing
@@bugz000I'll explain the algorithm, btw if anyone who reads this doesn't know an array is just a list of values and an index is a position.
• Find the lowest (min) and highest (max) values.
• Set range as max-min+1
• Create a new empty array, it should be as long as the range.
• Copy each value from the main array to the new array, but at the index of value-min.
For example, if min is 1 and the value you're at is 2, it'd go to index 1 (arrays start at index 0). Min would be at index 0 (beginning).
• Now array 2 is in order but may have some gaps if the main array isn't consecutive. E.g if the array doesn't have 3, index 2 (3-1) would be empty.
• Go through array 2, and if the index you're at isn't empty, copy it back to the main array, starting at main array's index 0 and increasing it every time you copy something to it.
Now every item in the main array is in order and there are no gaps.
@@bugz000 if i had two reds, and handed it to pidgeonhole, it’d take a hot minute cause they aren’t unique
if i gave it a red and an orange, it’d sort near instantaneously.
unless you want the explanation of how the sort works that’s all you’re getting
@@flarflecakes you also answered nothing
22:08 there are a million words in the english dictionary and, as someone who binges sorting algorithms from time to time, i could never possibly string enough words together to aptly describe how this makes me feel
-Susmogus😟😟😟😟abc?1234567890:((((()))))🙂hhhhhhh
Extratone
@@好吧-h6k p
*M I C R O W A V E*
Every emotion at once
Quick sort really lives up to its name. 2^15 elements sorted so fast that if you blink you'll literally miss it.
kid named quicksort killer:
Is this supposed to be a joke or something? I really just dont get it
@@belkYTif you look at the real time, it was like 30milliseconds
Quick sort is actually pivot sort
@@StavDevkid named pigeonhole sort:
34:34 scrambling through your bag to find the one thing you need
It is a good video to watch for sleep.
I agree
CALCULATED MIXTURE SORTS:
Max Heap Sort + Gravity Sort = Med Heap Sort
Flip Sort + Pancake Sort = Ultra-Flip Sort + Odd-Even Sort = Hyper-Flip Sort
Patience Sort + Tournament Sort + Unbalanced Tree Sort + Time Sort (Mul 10) = ??? (Musicombo. If you are watching this, please invent this calculated mixture sort right now.)
Double Selection Sort + Cocktail Shaker Sort = Cocktail Picker Sort
Lazy Stable Sort + In-Place Merge Sort + Rotate Merge Sort = ??? (Please invent this calculated mixture sort right now, or else. I beg you, Musicombo!)
Counting Sort + Pigeonhole Sort = Falconhole Sort
Circle Sort + Recursive Pairwise Sorting Network = Spiral Sort
Batcher's Bitonic Sort + Ternary Circle Sort = Tritonic Sort
Iterative Bitonic Sort + Comb Sort = ??? (Please invent this calculated mixture sort right now, for the sake of Musicombo!)
Iterative Odd-Even Merge Sort + Rotate Merge Sort = Iterative Odd-Even Rotate Merge Sort (I don't even know how to describe this algorithm sort, but some say you get your idea right to describe for these calculated mixtures of an algorithm sort.)
Iterative Pairwise Sorting Network + Recursive Pairwise Sorting Network = Ternary Pairwise Sorting Network
Recursive Pairwise Sorting Network + Last phase input on In-Place Merge Sort = Ultra-Recursive Pairwise Sorting Network
In-Place Merge Sort + Iterative Merge Sort = Optimized Iterative Speeding Merge Sort + Batcher's In-Place Merge Sort = Perpetual Speeding Merge Sort
Shell Sort + Comb Sort = Dash Sort (Whatever you call it, or just Massage Sort.)
Batcher's Bitonic Sort + Stooge Sort = Cocktail Bitonic Sort (Whatever you call it, or just Stooged Bitonic Sort.)
Exchange Bogo Sort + Bozo Sort (Nayuki version, only for JavaScript inputs.) = Shear Sort
Bubble Bogo Sort + Odd-Even Sort = Modern Odd-Even Sort (Not to be confused with Odd-Even Bubble Bogo Sort and I even truely know how to describe this algorithm sort.)
Droste's Recursive Pairwise Sorting Network is coming soon.
You do realize most of those are actually impossible, righ?
Tried to do my best with the audio here, guys... Hopefully my computer gets fixed soon so I don't have to record on the family Mac anymore!
Visit the channel Discord! discord.com/invite/2xGkKC2
I have no idea what’s happening but it’s cool so ima like it :D
32:36 is the start of a rave
Bubble sort: I am the best!
Cocktail shaker sort: I literally have 2 of you built in
Meanwhile pigeon hole sort🤑
@@yusufaltinbasakk2015Trash sort*
idk why but tournament sort was so satisfying
6:23 mongolian throat singing
Bottom-up Merge Sort (nr 32) is my favorite, it looks a little bit like a landscape at certain points
Heap sort contest!
Max heap: 68.321ms
Min heap: 69.491ms
Flipped min heap: 68.942ms
Weak heap: 52.065ms
Ternary heap: 64.444ms
Smooth sort: 96.486ms
Poplar heap: 82.909ms
Weak heap wins!
Weak Heap Sort: Pretty much the only sort that does not live up to its name in terms of speed.
@@nameisChannelID lol yep
What about pigeonhole sort? That one broke time
@@object.toString pigeonhole isn't a heap sort...
@@ATIHpss64HM oops, I forgot to read the title, and only read the times. Sorry about that
2:45 Look at the number of the swaps!
In place LSD, base 10, 800m+ swaps.
@@californium-2526 Radix sort (LSD) base 10 Writes to main array is about 2 billion
illuminati "66,66"
What if one day the algarithm just go like "fuck it, good enough" and not even finish
shatter sort on reversed cubic:
bogo sort (its trying its best)
Human sort lmao
Its crazy out the sort time and the visual time never line up with other sorts. Some take take visually like 20 seconds but take 15ms to finish, other visuals have like 1 min and only 10ms to finish.
maybe it's bc of varying sample sizes idk
are some of the slower sorting types more optimized for different situations or is there no real reason to use more than a handful of fast algorithims?
Slower sorts usually need less memory.
There are a number of factors like stability (which is needed if you want to, say, sort a deck of cards by both rank and suit), memory use, and whether there are different patterns (insertion sort is always super fast if (and only if) the list is already almost sorted for example, some only work if the array is a power of two large (which is why every array in the video (except bogobogosort) is a power of two large, so as many algorithms as possible can be shown), some algorithms are better able to handle if multiple items on the list are identical, etc), or simply the complexity of the code involved (anyone can code bubble sort in minutes, but something like timsort might take days if you have to do it from scratch and without documentation (ie you can't just use the standard Python library)).
Memory use is a big one. You may have noticed that most of the algorithms in the fastest (32,768) tier (such as most merge sorts) make heavy use of an auxiliary array, which is an instant doubling of memory use at minimum. Quicksort is considered the fastest general purpose sort precisely because it reaches the highest tier while being more memory-efficient than most alternatives (but it's not stable). Most slower algorithms also avoid using an auxiliary array (and often use even less memory than quicksort), but are good enough on small arrays and can outperform faster algorithms if there are certain patterns in the data. Algorithms that do use an auxiliary array also tend to outperform quicksort if certain patterns are present (while still being able to match it in the worst case), and are also more likely to be stable (such as most merge sorts and some radix sorts).
Some sorts are more art than anything practical. Bogosorts are designed to explore just how slow sorting algorithms can be for example.
@@watcher314159 Just saw this reply. Thank you for the very informative comment.
@@watcher314159 this is the kind of informative content I look at comments for
Are we ignoring the fact that Shatter Sort can’t be found anywhere else on the internet but it’s sorting 32,678 numbers in 7ms?
It's not a general-case sort! Also, that's an *estimated* time.
@@Musicombo idk whats going on but its satisfying so take my like
Shatter sort is just inaccurate pidgeonhole sort
This is a trip with captions on 😂
1:02:45 looks 3d!
Yeah!
You know an algorithm is bad when a list of 6 numbers is considered its greater limit
The pigeon sort is simply the most efficient sort there is. No need for another sort
time sort finishes in
@@theqwertycoder_alt The pidgeon hole-sort sorted 32 times more data.
When?
Idiot no, absolutely not
Quick sort with left\left pointers looks and sounds a lot like impending doom, it creates better suspense and expectation than some movies they make these days...
Selection Sort Analysis:
1/2 (n² − n) -> # of Comparisons
n − 1 -> # of Swaps
With data sets this big, the difference between O(n log n) and O(n^2) algorithms become very apparent.
1.6 Billions writes in main array, man Radix LSD Sort base 10 is hungry!
No, radix sort is efficient. That was inplace radix sort.
ok i really need a PUSHING SORTS TO EVEN SO MUCH MORE GREATER LIMITS I BEG YOU
Max that the program can go is 32k numbers. Sorry...
@@ishu4227No u can do 65536 and 131072+.
It's super easy
Wow this video taught my grandma how to breakdance
bro, i think she is having a seizure, and it not funny unlike alot of ppl say
@@ishu4227 You're literally the most annoying person there is omfg delete the reply
1:04:22 holy shit.. talking about luck
Forgot to include permutation sort:
Check every permutation of the list in order and see what permutation is the ordered one.
That's bogosort!
@@Musicombo Bogosort randomize the entire list, permutation sort, test every permutation of the list until its find the sorted one.
At a list [3,7,4]
It would check if the list [3,7,4] is sorted, it would fit its not, then it would check if the list [3,4,7] is sorted and would discover it is sorted, and stops there.
At bogo sort the next permutation to be checked wouldn't necessarily be [3,4,7] and also at bogosort there is a chance to check the same permutation more than once.
At permutation sort if the correct permutation of the list is the last one that will be checked it will need to check ALL permutations first, when talking about bogosort there is a chance the permutation is checked earlier.
@@exedeaththat's bogobogo sort
is nobody else talking about how bogo sort got it right first time??
Okay so in this video its the entire continental mainland of the WORLD that we are instantly measuring at the start of each sort, using Borg technology to scan the earths surface, obviously. THEN this sorts out every tiny little cove, spit, beach, fjord, inlet, and all until its a straight line you can put an exact number on 🤣🤣🤣
I feel like shell and comb would do better if they switched to insertion sort at the end
The patience sort is just a slow version of counting sort
No
Bro knows nothing
I’m here to watch bogo sort, saw bogo. 10/10 video; many bogo sorts
How does the bogo bogo sort works?(not the single bogo)
From en.wikipedia.org/wiki/Bogosort#Related_algorithms, "It works by recursively calling itself with smaller and smaller copies of the beginning of the list to see if they are sorted. The base case is a single element, which is always sorted. For other cases, it compares the last element to the maximum element from the previous elements in the list. If the last element is greater or equal, it checks if the order of the copy matches the previous version, and if so returns. Otherwise, it reshuffles the current copy of the list and restarts its recursive check."
@@kea2878 break it down
Thankfully I have vanced...
I like how you could've legitimately played 20:34 at 1x speed without slowing anything down and it wouldn't have been an absurd choice.
F I R E
How does insertion sort move values without swapping and without aux arrays?
I like to fall asleep to this. It's very calming ☺️
31:40 or a couple of seconds afterwards, it suddenly looks like a backgammon board. ... and at 31:54 ... and 32:04 32:14 32:26
33:45 the backgammon board is leaning over at a small but disturbing angle, as if I'm drunk or I'm on the deck of a ship in heavy seas.
it now has more elements than pixels oh god
tournament sort and patience sort are my favorite because they just go from chaos to instantly triangle
edit: also unbalanced tree sort
edit 2: and counting sort and pigeonhole sort wow i am forgetting a lot
edit 3: no bogo sort doesnt count
edit 4: flash sort is also cool
edit 5: i guess shatter sort? not really
Binary merge sounded beautiful
In-Place LSD Radix sort: Total chaos; Ultra seizure warning; to make someone have a seizure.
Bro really felt the need to show us 4 minutes of silly and slow sort
1:02:47 Damn..
this is the REAL entertainment.
Bubble bogo? More like bubble + odd/even
1:02:46
Nope.
Odd even cannot be combined with bubble sort as it is already a bubble sort variation. That's like trying to combine shell sort with insertion sort.
for wiki sort, what is it attempting to do?
Wtf, you got a 6 numbers bogo bogo in only 4/1.3, what kind of luck is that
How does flash sort work?
i have no idea why this exists but im glad it does
is there a use for these or are they just for fun?
Some of them are joke, some of them are just made by infamous sort like quick sort or radix sort and so on. They have practical purposes of their own.
In Place Radix LSD B10... over 1.5 BILLION writes to the main array. That's wild. All to stay in-place.
And the best part.. it's not even in-place. Just a little more memory conserving.
I think it should be considered an impractical sort because for a way better performance you can just use sample sort or flashsort
which has the best time?
Dude why the hell did this make me laugh 😭
because it's chipmunks on crack and sped up another 1000%
GNOME SORT IS ACTUALLY GOOD?
The best of shorting
22:30 Radix LSD 10
20:32
balt
id like to see a video like this except all sample sizes are the same, save for bogosort and the like
Pigeonhole sort was kinda overkill
Time sort Is the fastest
@@SuperTurtle0 pidgeon sorted like 32x more items. so it's an unfair battle. besides, its *estimated* time.
1:04:26
caption
hahahahahaha
How do you record this?
Radix in place is slower than my memory
Is there anything similar to this for mobile?
Fnf fans: yoo this song lit
(The song)
I just woke up to this at 2 am lol
Every other sorting algo when distribution sorts walk in 🙁🙁🙁
i can’t do this again… but i’m going to
18:53 Pac-Man everyone?
32,768 NUMBERS?!?
Good job Bogo sort
It would be funny if you did a miracle sort video and you edit it to make jesus swoop in and Heap Sort the array for you
can someone please explain what's actually happening?
line get organize
@@definitelynotklip Thank you Ron
Different sorting algorithms, the video is illustrating how each algorithm works and performs.
bogo sort world record
Idk why this is fun for me
14:42 thumbnail
1:04:33 8 million shuffles. average 24883200 shuffles so it got lucky
WOOP!!!
flash sort op
One billion writes into the main array. Christ
not yet, poor radix didnt get 1 bil
wait, did one get a billion?
So bubble is the worst sort algorithm?
One of? Probably.
@@Musicombo I dare you to rank ALL the sorts worst to best.
ALL OF THEM.
*EVERY.* *SINGLE.* *ONE.*
The? No. BogoBogo is.
in place lsd radix sort base 10 *a billion writes*
not quite... :(
I came here from kraccbacc
50:20 fnf hellbreaker be like:
enjoying this but not understanding any of it makes this a baby sensory video for adults
NOOO RADIX DIDNT GET 1 BILLION NOOOOO
ASMR be like
bogo sort wr: 6.5 ms!
funniest shit i ever seen tbh
fnf fans: yo this song is lit
Honestly I'd like to see all of these sorts using the same amount of numbers
I've answered this question multiple times before, but that would lead to a very uninteresting video considering Bogo Bogo Sort can only be fed up to 6 numbers before the amount of time it takes to finish becomes unreasonable.
@@Musicombo oh, I know, it would just be interesting to see exactly how inefficient some sorting methods would take.
Fair enough!
@@Musicombo maybe you can sort theeeeee categories of sorts, from fast to slow, andn only compete the fast sorts with the fast, middle withh t he middle, and slow withthe slow. idk about bogobogo tho
Silly sort 😂
do bogo with 16 numbers
16! Comparisons and Swaps
How about Hexagon Root Sort? It means: "HxRt Sort"!
@@wagnerramosmidichannelabso514 how would it work?
do bogosort with 10k list you wont :)
Time sort gets 1st place for creepiest sort of all time!