It’s like I’m going shopping for sorting algorithms

@mathguy37

10 ай бұрын

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.

@vinccool96

10 ай бұрын

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!

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!

@ferociousfeind8538

10 ай бұрын

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!

@gallium-gonzollium

10 ай бұрын

There is an optimized grailsort called “Holy Grailsort”, I just love how fast a stable inplace alg can get :D

@omayoperations8423

10 ай бұрын

I'm biased because I met Tim Peters, the guy who came up with Tim sort.

@TaranVaranYT

10 ай бұрын

Every algorithm. Top one? Pigeonhole Sort. The process goes like this: 1. Check the list twice. 2. Done!

@simeondermaats

10 ай бұрын

I've been writing a sorting algorithm visualiser in Rust for a while now and gnome sort is the most fun to watch running.

Wake up babe, new Kuvina Saydaki sorting algorithms video just dropped!

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!

common kuvina banger

A new Kuvina upload is a good time to be had

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.

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.

@meowis526

10 ай бұрын

Why dont you make aweonaosort (when randomizing it compares randomly instead of swapping)

@Ryann9

2 ай бұрын

What if you combine miracle and bobo sort and create a sorting algorithm that basically just repeatedly outputs the list without randomizing?

kuvina upload after i discover their channel less than a week ago? nice i already love your videos

Great video! Thanks for the excellent explanation.

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.

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’m here for the joke sorts, but still learn the legit ones. Btw, really happy to see the joke sorts I’ve suggested.

Love these videos ❤❤❤

This is so cool!!

i love your self portrait

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

i love this series

Some implementations of intro sort actually use insertion sort for list sizes under 32.

Huge Kuvina W

💛🤍💜🖤

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.

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.

These videos are so fun

banger !!

Is there an algorithm which looks at the list, does some tests, and then decides which algorithm would be best to use?

@drunkendog4469

10 ай бұрын

I'd guess that'd take longer than just sorting the list with any given sorting method

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

@Kuvina

10 ай бұрын

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.

@Kuvina

8 ай бұрын

Expect it this week!

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.

@Matyanson

7 ай бұрын

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?

@TaranVaranYT

7 ай бұрын

@@Matyanson yes

the Bogo^2 is hilarious!

yay uplaod

I actually burst into laughter when you explained sleep sort

How do you organize these sorting algorithms?

@Kuvina

10 ай бұрын

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 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.

@MichaelDarrow-tr1mn

5 ай бұрын

wait that's just shell sort

@i_like_treins3449

3 ай бұрын

​@@MichaelDarrow-tr1mnlol

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!

@therealelement75

6 ай бұрын

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.

@mr.duckie._.

6 ай бұрын

@@therealelement75 so someone invented this before? and yes it does just swap incorrect elements, that's the idea it's built on

@therealelement75

6 ай бұрын

@@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.

@mr.duckie._.

6 ай бұрын

@@therealelement75 aight it's now conveyor belt sort official

@therealelement75

6 ай бұрын

I think it's stable (if you get the "where is this supposed to go properly)

Will you cover Silly Sort??

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.")

Try Bozo sort. It's like Bogo, but instead it swaps two items at random instead of shuffling the list.

You need more subscribers

I thought in-place algorithms mutate the original array while non-in-place algorithms return a new array which is sorted

I’m nb so I’m happy that I found someone who likes science and math :3

@thumbgoblin4716

10 ай бұрын

sameeee

@Not_Tails

9 ай бұрын

No way, Temmie is non-binary?!?!?!?!?

@temmie1662

9 ай бұрын

YEEEEEEEEEEEEE@@Not_Tails

@Not_Tails

9 ай бұрын

@@temmie1662 hey :3

@temmie1662

9 ай бұрын

@@Not_Tails >:3

Finally

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.

EVERYONE needs to understand the Stalin Sort. !

identity crisis sort 2: instead of alternating between modified merge/quick sort, randomly choose one of them

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.

Whats the deal with pigeonhole sort? It looks like you just look at the list once and you're done.

@Kuvina

10 ай бұрын

I believe pigeonhole sort is basically the same concept as counting sort, which I covered in part 1!

@hdckighfkvhvgmk

10 ай бұрын

​@@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 didnt to do my homework and forgot eveything but thanks for including bogobogo sort -liz

Sample sort feels like multi pivot quicksort.

Alright, sort this list! Miracle sort: I don't think I will.

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

@origamiscienceguy6658

10 ай бұрын

That's some weird hybrid of merge and insertion sort, which negates the advantages of both.

@tobyconner5827

10 ай бұрын

@@origamiscienceguy6658 precisely

Best sort is RADIX LSD SORT IN PLACE BASE 10

I thought Stalin sort was going to be that you just define a new ordering under which the list is already sorted.

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.

commenting for the (SORTING) algorithm (, HA)

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

16:25 you misspelled nlogn

Right now I'm eating bread 🍞

@Kuvina

5 ай бұрын

I love bread! 😍🍞

Reverse time sort. Start with a sorted list, then scramble the list arbitrarily. Now reverse time.

i will never learn how the heck radix sort works

@GamemodePC

4 күн бұрын

now i do

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)

@FenrizNNN

10 ай бұрын

They covered it on part 2. This is (kind of) part 3.

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).

Your little avatar is so silly

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)

@vaclavtrpisovsky

10 ай бұрын

Next - trigger warning - not all sorting algorithms are binary!!

Can u stop using a white background it hurts my eyes at night