Explaining EVERY Sorting Algorithm: Variants and Hybrids
ฝัง
- เผยแพร่เมื่อ 22 พ.ค. 2024
- This is the 3rd episode in my series explaining every sorting algorithm. In this video, I explain the most widespread hybrid and variant sorting algorithms.
part 1: • Explaining EVERY Sorti...
part 2: • Every Sorting Algorith...
twitter: / kuvina_4
instagram: / kuvina_4
Chapters:
0:00 Why Hybrid Algorithms?
2:36 Quick Sort with LL Pointers
3:01 Dual Pivot Quick Sort
3:55 Proportion Extend Sort
4:42 Intro Sort
5:23 Pattern-Defeating Quick Sort
7:08 Tim Sort
8:56 Iterative Merge Sort
10:00 In Place Merge Sort
11:12 Weave Sort
11:30 Rotate Merge Sort
13:01 Quad Sort
14:40 Block Sort
16:18 Weak Heap Sort
19:09 Smooth Sort
22:35 Poplar Sort
23:05 Ternary Heap Sort
23:39 In Place MSD Radix Sort
24:57 Binary Quick Sort
25:21 In Place LSD Radix Sort
26:05 American Flag Sort
27:10 Burst Sort
27:34 Spread Sort
28:31 Sample Sort
29:18 Proxmap Sort
29:37 Cartesian Tree Sort
30:09 Stalin Sort
31:16 Sleep Sort
31:36 Miracle Sort
32:00 Bogobogo Sort
33:04 Power Sort
33:50 Identity Crisis Sort
34:20 Outro Sort
#sorting #algorithm #computerscience - วิทยาศาสตร์และเทคโนโลยี
It’s like I’m going shopping for sorting algorithms
Yeah and sort those sorting algorithms with more sorting algorithms
Great video! I especially like how you used Stalin sort as an excuse to talk about the longest increasing subsequence.
I tried to do a merge sort variant which partitions by basically doing "stalin sort" but instead of deleting it moves unsorted elements into a new sublist, which is then sorted recursively and merged with the already sorted list. In theory an already sorted list should be O(n). I also just realized an improvement, it might be nice so save the index where the first unsorted element was extracted to skip the first few comparisons in the merge step too. I didn't really look into improving it much since it's rarely better than regular Merge Sort for randomized test arrays.
I’ll name it Mao Sort. You send them to the reeducation camp instead of to the gulag.
love your videos! they are very clear and concise, and i especially appreciate that you explain benefits AND drawbacks, as opposed to just benefits
10:42 I know it's not covered here, but the O(n^0.5) space combine-halves is one of the block sort variants, aptly named sqrtsort!
Great video, thank you for putting light on some of these cool combination algorithms. i'm happy your channel has been doing well, you make great informative stuff!
Love your visualizations and nice explanations. Also, though i don't know if it's on purpose, but your voice always places emphasis just where it needs to in order to keep my attention. Like, your inflections are really attention keeping.
common kuvina banger
Great video! Thanks for the excellent explanation.
What's your favorite algorithm?
Leave a comment or reply. Mine might be shell sort because of its extremely small code size, and unique non integer power time complexity!
I've always been a fan of merge sort because the concept is amazingly simple but also surprisingly fast. I disliked quicksort because I didn't understand at all what it was doing- when people explained it, they would get into implementation quirks which unnecessarily obfuscated the logic to it. Once I understood what it was doing, I found myself liking it too, though. What a champ, quicksort is!
There is an optimized grailsort called “Holy Grailsort”, I just love how fast a stable inplace alg can get :D
I'm biased because I met Tim Peters, the guy who came up with Tim sort.
Every algorithm. Top one? Pigeonhole Sort. The process goes like this:
1. Check the list twice.
2. Done!
I've been writing a sorting algorithm visualiser in Rust for a while now and gnome sort is the most fun to watch running.
kuvina upload after i discover their channel less than a week ago? nice i already love your videos
I like how a lot of algorithms fall back on either heap sort or insertion sort, almost like you should just use a heap instead of a list.
A new Kuvina upload is a good time to be had
Love these videos ❤❤❤
Wake up babe, new Kuvina Saydaki sorting algorithms video just dropped!
I'm currently very tired, but I just had to watch this video before going to bed because your other two videos have already been amazing. I was definitely not awake enough anymore, though. xD
i love your self portrait
I’m here for the joke sorts, but still learn the legit ones.
Btw, really happy to see the joke sorts I’ve suggested.
This is so cool!!
i love this series
On proportion extend, finding the median without sorting the list first is possible, but only if the list is only of integers, and finding it takes O(partition) time. Optionally, the current item is comp-swapped with an adjacent item during the search, which makes it called bubblescan quicksort
Idk what this would be named, but hear me out:
One of the most efficient sorting algorithms ever created, bogosort, wastes some time, mainly in three steps: checking if the list is in order, randomising it and finishing. Miracle sort solves this partially by eliminating the very time-consuming step of randomising; however, it has come to my attention that checking if the entries are ordered is itself quite time-consuming.
The new and improved bobo sort (from the Spanish word "bobo", meaning "dumb") just randomises the list and outputs it, then repeat. It is probably at some point going to give the right answer. The program may not terminate (specifically, it doesn't terminate for lists with mire than or equal to 1 possible ordering), so be careful when implementing.
Why dont you make aweonaosort (when randomizing it compares randomly instead of swapping)
What if you combine miracle and bobo sort and create a sorting algorithm that basically just repeatedly outputs the list without randomizing?
Boho sort: I’ll just try again! (Randomizes the list) no, still not sorted. (Tries again)
Miracle sort: is it sorted? No? I give up.
the Bogo^2 is hilarious!
Huge Kuvina W
Some implementations of intro sort actually use insertion sort for list sizes under 32.
These videos are so fun
I have been thinking of a sorting algorithm called Spread Sort. The process goes like this:
If the list size is even:
1. Take the 2 items in the center of the list and move them to the outer parts of the list.
2. Repeat the same with the 2 adjacent to the center. Continue doing this until you reach the outer parts.
3. Reverse each sequence of items in groups of increasing size (starting at 2) including those that get cut off.
4. Once you reverse the whole list (when group size = list size), check the 2 values at the left, and swap them if the left one is larger, then move the point of focus to the right by 1, and swap those. Keep doing this until you swap the 2 rightmost values. Continue doing Bubble Sort like this for 1 more cycle.
5. Do steps one and 2 again.
6. Check for sublists, and extract the one with the most consecutive items (an item has to be equal to the ones on both sides give or take).
7. Group the extracted sublist with the item that is 1 less than the smallest one. Repeat steps 1-7 until the sublist is the same size as the main list itself.
If the list size is odd:
1. Take the 2 items next to the center of the list and move them to the outer parts of the list.
2. Repeat the same with the 2 adjacent to those. Continue doing this until you reach the outer parts.
3. Reverse each sequence of items in groups of increasing size (starting at 2) including those that get cut off.
4. Once you reverse the whole list (when group size = list size), check the 2 values at the left, and swap them if the left one is larger, then move the point of focus to the right by 1, and swap those. Keep doing this until you swap the 2 rightmost values. Continue doing Bubble Sort like this for 1 more cycle.
5. Do steps 1 and 2 again.
6. Check for sublists, and extract the one with the most consecutive items (an item has to be equal to the ones on both sides give or take).
7. Group the extracted sublist with the item that is 1 less than the smallest one. Repeat steps 1-7 until the sublist is the same size as the main list itself.
I don't understand most of what you meant. Could you please write that in pseudo code?
"move them to the outer parts of the list" do you mean to move them to the edge of the list(start&end)? Or just move them by 1 in that direction?
@@Matyanson yes
I’m nb so I’m happy that I found someone who likes science and math :3
sameeee
No way, Temmie is non-binary?!?!?!?!?
YEEEEEEEEEEEEE@@Not_Tails
@@temmie1662 hey :3
@@Not_Tails >:3
I've always had a soft spot for cocktail shaker sort.
I also came up with an adaptive heap sort that works by heapafying sublists and then comparing their roots... never got to test it out, though because I don't have the code skill level.
I actually burst into laughter when you explained sleep sort
banger !!
Quick question: What if you have a Min Heap Sort, but instead of swapping and replacing the tree nodes, it "starts over" aka builds a "new" heap but leaves the min from the previous heap alone? I can imagine it COULD be faster, but also could be much slower and extremely inefficient
I believe it is slower. Even if the build max heap operation doesn't make any swaps, it still needs O(n) comparisons to make sure each piece is greater than or equal to its parent.
💛🤍💜🖤
Hey Kuvina, any news on the 'Block Sort Explained' Video? I am really looking forward to that as I still don't 100% understand block sort and its different variants.
Expect it this week!
yay uplaod
i invented a sorting algorithm recently: cycle sort. oh wait that name is already occupied
so i'll call it.. loop sort.
here are the steps:
1. check the list for any elements already in their final position
2. cycle through the elements not in their final position
wait i need to explain how to cycle
[[cycling works like this: you take all elements not in their final position and move them to the right. if there are any elements in their final position, you move the piece from the left of that to the right. however, if there's an element that has to be cycled on the right edge of the screen and it can't go anywhere, move it to the left-most spot. all the pieces cycling cycle at once]]
3. check again if any elements landed onto their final position. if not, go back to step 2 and do that.
4. if no elements can be cycled, that means all the elements are on their final position, so the list is sorted.
the extra thing is this algorithm doesn't check what the elements are, if which is the smallest or largest, nononono. it only cares if an element is in their final position or not, and
the maximum amount of times a cycle can happen is the amount of elements in the array minus one.
time complexity: not sure
worst and best case: not sure
stability: no
if anyone wants to analyze it or improve it, go ahead!
so (idk how to do it)
check all unchecked and not good items for if good
exclude all good items
cycle
that's one loop
checking an element takes n*(n-1)
separate the list into {not good part} {good part} {not good part}
move rightmost element to left of next not good list
merge the lists
requires extra storage (size is about n)
I think best case is n*(n-1)
worst case is probably equal to or bigger than n(n*(n-1)
also, on average, 1 element would already be correct in a list.
@@therealelement75 so someone invented this before?
and yes it does just swap incorrect elements, that's the idea it's built on
@@mr.duckie._. yeah you've got big cycle sort (my name recommendation)
you could call it conveyor belt sort
you've got a cool, albeit slower version of Cycle Sort.
@@therealelement75 aight it's now conveyor belt sort official
I think it's stable (if you get the "where is this supposed to go properly)
Is there an algorithm which looks at the list, does some tests, and then decides which algorithm would be best to use?
I'd guess that'd take longer than just sorting the list with any given sorting method
Try Bozo sort. It's like Bogo, but instead it swaps two items at random instead of shuffling the list.
I thought in-place algorithms mutate the original array while non-in-place algorithms return a new array which is sorted
Will you cover Silly Sort??
I came up with a sorting algorithm.
1. Sort pieces with even indices recursively.
2. Sort pieces with odd indices recursively.
3. Perform Insertion Sort on the now mostly sorted list.
wait that's just shell sort
@@MichaelDarrow-tr1mnlol
identity crisis sort 2:
instead of alternating between modified merge/quick sort, randomly choose one of them
A great joke algorithm I saw recently is Ba Sing Sort, which completes in O(1) time:
1. Convince the user that there are no unsorted elements in the list.
(To spoil the joke, it's a reference to Avatar: The Last Airbender, where peace in the city of Ba Sing Se is maintained by brainwashing people. "There is no war in Ba Sing Se.")
heres an incredibly efficient sorting algorithm idea, please tell me if it's already been named:
1. split the list into sublists each of which contain 1 element (ie [2,4,3,1] -> [[2],[4],[3],[1]]
2. merge and sort adjacent pairs:
2a. simply append the second sublist to the first ([[2],[4],[3],[1]] -> [[2,4],[3],[1]])
2b. if the first element of the merged sublist is smaller than all subsequent elements, move to the next element; if not, move the first element to the end of the sublist and repeat with the new first element
3. blah blah blah continue merging and repeating steps until the list is sorted
heres what the steps would look like with [2,1,4,5,3]:
[[2],[1],[4],[5],[3]]
[[2,1],[4],[5],[3]]
[[1,2],[4],[5],[3]]
[[1,2],[4,5],[3]]
[[1,2,4,5],[3]]
[[1,2,4,5,3]]
[[1,2,5,3,4]]
[[1,2,3,4,5]]
sorted!!
i know this is a pretty vague explanation so i can (try) answer questions as needed
That's some weird hybrid of merge and insertion sort, which negates the advantages of both.
@@origamiscienceguy6658 precisely
You need more subscribers
EVERYONE needs to understand the Stalin Sort. !
Alright, sort this list!
Miracle sort: I don't think I will.
Creationist Sort: the list is in its current order because a greater power willed it so, and we shouldn't defy this greater power, therefore it's already in its final state.
How do you organize these sorting algorithms?
For the most part, they fall into 5 categories, variants of quick sort, merge sort, heap sort, radix sort, and bucket sort. So I covered them in that order since that's the order in which I covered the originals in part 1.
I thought Stalin sort was going to be that you just define a new ordering under which the list is already sorted.
Sample sort feels like multi pivot quicksort.
Finally
Here's a joke algorithm idea: the oracle sort
You give the program the data, and then it goes to consult an oracle for your desired list, then it will replace the old list with the new list
edit:
The time complexity would be 2m=h where 2 is the walking speed of the algorithm m is the distance from the city of Delphi in miles making h the time it takes to get there in hours
Heres another sorting algorithm you haven't covered: bozo sort, basically the bogo sort but instead of shuffling the entire array, you randomly pick 2 elements to switch.
At what point does it become faster to sort location references rather than the actual data? Asuming you copied out the part of the data your sorting by.
i didnt to do my homework and forgot eveything but thanks for including bogobogo sort
-liz
16:25 O(nlgon)
Best sort is RADIX LSD SORT IN PLACE BASE 10
commenting for the (SORTING) algorithm (, HA)
Whats the deal with pigeonhole sort? It looks like you just look at the list once and you're done.
I believe pigeonhole sort is basically the same concept as counting sort, which I covered in part 1!
@@KuvinaI am curious as to what makes it different/better(?) than counting sort. Most likely it's that pigeonhole has more specific use cases but is faster for those cases.
i will never learn how the heck radix sort works
Right now I'm eating bread 🍞
I love bread! 😍🍞
Reverse time sort. Start with a sorted list, then scramble the list arbitrarily. Now reverse time.
16:25 you misspelled nlogn
You forgot the best one, quantum bogosort. Randomize the list, then delete every universe in which the list is not sorted. It has O(1)
They covered it on part 2. This is (kind of) part 3.
Your little avatar is so silly
Another joke sorting algorithm that I like is sleep sort. How it works you create a new thread for each element of the list, then on each thread you call a sleep function with the time equal to the corresponding element. Then as each sleep finishes you add that element to the new list. This technically has a time complexity of O(n).
the array elements are a rainbow... what's next, you're going to tell me pronouns are part of most languages? smh woke moralist
(opening card is v cool btw)
Next - trigger warning - not all sorting algorithms are binary!!
Can u stop using a white background it hurts my eyes at night