Every Sorting Algorithm Explained in 120 minutes (full series)

Рет қаралды 41,124

Күн бұрын

This is a compilation video of the 4 existing sorting videos on my channel.
Visualizations: • Visualizing 70 Sorting...
• Explaining EVERY Sorti...
• Every Sorting Algorith...
• Explaining EVERY Sorti...
• The Perfect Sorting Al...
Corrections / clarifications: none so far
Resources I mentioned in section 4:
itbe.hanyang.ac.kr/ak/papers/t...
en.wikipedia.org/wiki/Block_sort
github.com/BonzaiThePenguin/W...
github.com/HolyGrailSortProje...
habr-com.translate.goog/en/ar...
Chapters:
0:00 Intro
1:34 Selection
2:04 Double Selection
2:30 Insertion
3:07 Binary Insertion
3:56 Bubble
4:28 Shaker
4:46 Asymptotic Notation
7:40 Finding Time Complexity
9:48 Quick
11:51 Merge
13:10 Stability
14:11 Space Complexity
15:57 Heap
18:46 Comb
20:05 Shell
21:28 Radix LSD
25:28 Radix MSD
26:11 Bucket
28:58 Counting
30:26 Spaghetti
31:03 Gravity
32:33 Pancake
33:45 Bogo
34:53 Section 2 Intro
35:16 Cycle
35:55 Patience
37:04 Exchange
37:49 Odd-Even
38:12 Circle
39:13 Merge-Insertion
40:13 Tournament
41:00 Tree
42:09 Gnome
42:41 Library
43:28 Strand
44:20 Topological Sorting
45:18 Sorting Networks
46:57 Bitonic
48:43 Odd-Even Network
49:07 Pairwise Network
49:42 Why Hybrid Algorithms?
52:34 Quick LL
52:59 Dual Pivot Quick
53:53 Proportion Extend
54:40 Intro
55:21 Pattern Defeating Quick
57:06 Tim
58:54 Iterative Merge
1:00:20 In Place Merge
1:01:10 Weave
1:01:42 Rotate Merge
1:02:59 Quad
1:04:37 Block Sort Preview
1:05:08 Weak Heap
1:08:19 Smooth
1:11:23 Poplar
1:11:52 Ternary Heap
1:12:26 In Place Radix MSD
1:13:45 Binary Quick
1:14:09 In Place Radix LSD
1:14:53 American Flag
1:15:57 Burst
1:16:21 Spread
1:17:19 Sample
1:18:05 Proxmap
1:18:24 Cartesian Tree
1:18:56 Section 4 Intro
1:23:05 Outline
1:25:29 Sqrt
1:30:05 Block
1:36:39 Wiki
1:41:57 Grail
1:50:07 Stooge
1:51:06 Slow
1:52:08 Quantum Bogo
1:52:33 Stalin
1:53:36 Sleep
1:53:56 Miracle
1:54:20 Bogobogo
1:55:24 Power
1:56:09 Outro
#math #sorting #algorithms #explained #math #computerscience

Пікірлер: 144

@Kuvina 27 күн бұрын

Visualizations: kzfaq.info/get/bejne/i9dmiLWr1J_VZps.html I hope you enjoyed learning about algorithms! And for returning viewers, I hope you enjoy the trip down memory lane!

@Johnny_Franco-12_Scratch 21 күн бұрын

こんにちは、クヴィナ・サイダキ！

@CaptainDangeax 19 күн бұрын

Great vidéo. I'm gonna play with my C128 ASM just for the fun of it, trying to implement some of them and programming the VDP

@Patricia_Taxxon 26 күн бұрын

genuinely love the way you've adapted this into a worlthwhile viewing experience rather than just a compilation, the little titles are so cute, and the new bits of voiceover make this feel like it was always supposed to be one huge video.

@M113sAldrich 6 күн бұрын

I was going to make that Adam Sandler joke but I understand why you are here

@maadneet 27 күн бұрын

Have I watched each of the individual videos before? Yes. Will I watch this compilation? Absolutely.

@wyattstevens8574 26 күн бұрын

There's also a visualization-only companion!

@maadneet 26 күн бұрын

@@wyattstevens8574 Watched that too!

@Patricia_Taxxon 27 күн бұрын

kuvina i am rooting for you

@jan_Eten 27 күн бұрын

mood also omg is ðat patricia taxxon ( 'o') i loved your love rap explanation in rhythm heaven iceberg megamix ( ^u^)b

@MarkusIfquil 27 күн бұрын

patricia ily

@RadioactiveBluePlatypus 27 күн бұрын

Omg hii you're my favorite autistic furry youtuber yippee! /genuine Helped me realize I'm autistic myself

@temmie1662 26 күн бұрын

@@RadioactiveBluePlatypusoh oh hi /gen

@paper2222 26 күн бұрын

our favorite enby buddy

@MonitorLizardGaming 27 күн бұрын

Two hours of high quality and well-thought-out content? Am I dreaming??

@yellowmarkers 27 күн бұрын

There goes my plan to make a sorting algorithm explanation. I can just redirect people here now.

@EntergeticalakaBot 27 күн бұрын

There goes the ideas, being used by others

@realmless4193 26 күн бұрын

Just checked out your channel because of this comment. Did subscribe.

@samanther511 26 күн бұрын

The idea of sorting networks is really reminding me of how factorio balancers work

@robertmauck4975 17 күн бұрын

That was my first thought too

@octopodes_nuts 2 күн бұрын

I would not be surprised if there's Factorio builds that contain otherwise-unknown algorithms that beat any documented method, whether sorting or some other interesting task

@mistymysticsailboat 22 күн бұрын

does anyone else ever get annoyed at Quick Sort being called Quick Sort, like that just feels unfair to the rest of the sorts. why isnt it called like "Partition Sort" or something

@mistymysticsailboat 22 күн бұрын

and like it Clearly has weaknesses. it is horrible on an already sorted list.

@Kettwiesel25 20 күн бұрын

Pivot sort is more descriptive I think

@ultra824 23 күн бұрын

Here's a favorite joke algorithm of mine: Intelligent Design sort. It works like this: First, observe that the probability of the array being in the exact order that it's in by chance is 1/(n!), this is so unlikely that we must conclude that the array was put in that order by an intelligent Sorter, who must have sorted the elements by some metric beyond our mortal comprehension. This means that any change we might make to the array would actually make it _less_ sorted, which would be against the Sorter's plan. Therefore, the algorithm is complete. This has O(1) Time Complexity.

@FinnPlanetballs 27 күн бұрын

20:38 there is an among us hidden in the purple bar

@jan_Eten 27 күн бұрын

yeah i know

@wyattstevens8574 26 күн бұрын

Didn't notice that!

@theunknown4834 23 күн бұрын

Really something among us

@Spax_ 15 күн бұрын

went looking for this comment

@mrtopper930 18 күн бұрын

I’m learning math and science for college majors at 10:30pm. I fell proud.

@ManicVolcanic 19 күн бұрын

Very nice video. Regarding the bonus section at the end -- you'll no doubt be pleased to hear that the latest SIGBOVIK conference introduced bogoceptionsort! Bogosort may accidentally sort very small lists correctly in only a few iterations. To prevent this, bogoceptionsort first shuffles the *order of the lines of code* that make up the bogosort implementation, then attempts to run it, then checks to see if the list is sorted. This effectively pads the number of elements in the list, making it perform extremely poorly for even lists of size, like, five.

@colly6022 27 күн бұрын

bubble sort and shaker sort are definitely the most intuitive for me, as i've unknowingly been doing smth very similar my whole life for real-world situations!

@HesterClapp 26 күн бұрын

I think insertion sort is more intuitive than bubble sort. Bubble is easier to code, but it's harder to convince yourself that it works

@not_estains 13 күн бұрын

i use radix lsd base 2 sort irl

@evanzieg 27 күн бұрын

I'm a huge fan of all of the icons! They are all very clean and well designed! Great work on all the visuals and research in the series!!

@mithrilbookofmystery 16 күн бұрын

genuinely I love this so much. I do not know enough math to keep up with your descriptions 100% of the way, but what I can parse is genuinely very interesting. I love sorting algorithms, and I love learning more about how they work, even if I can never fully understand it. Thank you so much for this video! I was enraptured all the way through.

@mithrilbookofmystery 16 күн бұрын

Ahhh I lied I was actually still watching - near the beginning - when I wrote this but by god I am still enraptured. I'm going to start commenting on the little things I'm enjoying as I go along, because there are many, and I couldn't stop myself at just the one comment. First of all: I love your explanation of the use cases for these algorithms. Or, well, I'm currently just in merge sort, I'm unsure if you keep doing it down the line, but still! it's cool to know the pros and cons of each sort, and why one algorithm would be used over another, as in your city name sorting example.

@mithrilbookofmystery 16 күн бұрын

20:38 >:0!!!!!

@epikoof 26 күн бұрын

gotta admit, 80% of block sort flew over my head after sqrt, but i loved this entire video anyway, thank you so much

@krabman6297 22 күн бұрын

Someone should make a paranoid sort algorithm, like bubble sort, but it swaps items a random amount of times just to make sure it's actually swapped, and should have a save function it spams just in case it crashes. You can also make it randomly mess up or starts over completely, maybe even go through twice and compare the two finished sorts to see if it got the same outcome before determining if it's sorted or not

@migueltorrinhapereira7473 24 күн бұрын

This series of videos inspired me to create a sorting algorithms visualization that runs on my CASIO graphical calculator, I implemented 16 different algorithms and it was really fun. Thank you. Great video, very helpful and interesting.

@lerq0ux 23 күн бұрын

I came looking for one of those “every __ explained” videos but i got something much better

@ishu4227 8 күн бұрын

49:56 this feels so much like a meme template and i love it

@Skyb0rg 26 күн бұрын

1:52:30 Quantum bogosort is actually implementable, but would be O(2^n) in all cases, since you need to spend time creating those 2^n “worlds” to destruct. There is another interesting sorting algorithm, which is the “differentiable sorting” algorithm. It takes in a list and returns the permutation required to make it sorted, but the entire algorithm can be differentiated (needed in ML and for incremental computation).

@MichaelDarrow-tr1mn 21 күн бұрын

actually o(n!)

@ceremyjlarkson9475 27 күн бұрын

20:38 Quite suspicious indeed

@josephgaming3357 27 күн бұрын

I kinda want to know what all the algorithms would look like if you started with a reverse order list instead of a shuffled list. is there somewhere I can see that?

@SysFan808 23 күн бұрын

sorting algorithm i made (and probably many others too) so, i started with bogo, but then tweaked the randomiser function. it was originally picking 2 random values and swapping them i changed that "swapping" to "comparing" them. i don't know what to call it, but it does work quite well as a sorting algorithm.

@antoninduda9078 20 күн бұрын

I think it's called either bubble bogo sort or exchange bogo sort

@wiktorszymczak4760 18 күн бұрын

Forever proud of actually using bogosort back in uni and getting it accepted

@skittlez0496 17 күн бұрын

A variation on quantum bogo sort (without the universe destruction): Step 1) go through the entire list to see if it’s sorted, also counting what n is in the process Step 2) with n! parallel processors and n! auxiliary arrays, distribute each element evenly into each open spot in each array, which guarantees that each array is distinct* Step 3) because each auxiliary array is necessarily distinct, and we have n! number of them, exactly one must be sorted. Simply use all our parallel processors to comb through them simultaneously to find the sorted list. Boom, the fasted on average sorting algorithm possible (time complexity of n) The only issue would be the space and processing it requires…

@skittlez0496 17 күн бұрын

*if the list doesn’t contain strictly distinct values, there will be multiple auxiliary arrays which are sorted, but still only one that is sorted stably We can make this algorithm stable by taking the first auxiliary array (which is necessarily just a copy of the original list) and use it as a “stable” memory storage to help find the one true stably sorted list

@epikoof 26 күн бұрын

kuvina, patricia taxxon and jan misali should all collaborate sometime

@jursamaj 26 күн бұрын

22:10 I may have mentioned this in the original video, but radix sort *can* be used on strings (as long as characters have a fixed-size representation). It's most efficient with fixed-size strings, but can even be used on variable length strings.

@kaderen8461 21 күн бұрын

i will not need this information. but it begs to be watched

@Musicombo 20 күн бұрын

Hey, just to letcha know: you are more than welcome to join The Studio so you can stay updated on Holy Grailsort's progress (once we come out of hiatus, which is hopefully soon)! ❤❤

@joelicandi2586 22 күн бұрын

Fantastic Work !! very impressive

@RT777 5 күн бұрын

Stumbled across this awesome video and liked it 5 minutes in. It’s great, but I would suggest adding a touch more emotion in to it. Great video!

@CombineCubing 26 күн бұрын

How much sorting algorithm do you want? Me: *_Yes_*

@Musicombo 26 күн бұрын

Once again, your explanation for Grailsort makes me smile ❤

@arcainchaos 25 күн бұрын

I am less than a minute into the video and I need you to know that I love you

@etaosin 5 күн бұрын

Great work, congratulation. Certainly watch one time is not enough. But understanding level again increased in my situation.

@12times12_ 23 күн бұрын

bitonic sort visualizes the swaps that are needed to make a belt balancer in the video game Factorio lol

@ERRORRubiksZeraBrand 20 күн бұрын

i am trying to make a sorting visualizer in python by using your terminal and using pygame for the sounds. i didn't understand many sorting algorithms but this helped me understand some of the algorithms. i also included one of your sorting algorithms (baiai sort) inside. thank you for the explanation and peace.

@augie279 20 күн бұрын

I don’t understand any of how block sort works but I’m glad computers do

@namethathasntbeentakenyetm3682 27 күн бұрын

Now I can understand the things

@DavidvanDeijk 24 күн бұрын

very enjoyable, thank you. shell sort is indeed a favorite.

@mommyuki 27 күн бұрын

new Kuvina video! I already love it

@TheBalthassar 27 күн бұрын

I'm pretty sure I said this on the original video, but when we got to the sorting networks and bitonic, my mind goes to Factorio belt management theory.

@thumbgoblin4716 27 күн бұрын

ive already seen all 4 videos, is there anything new in this one?

@Kuvina 27 күн бұрын

not really I just redid some audio and visuals to make it easier to watch, and added segues between the sections

@mitchellbailey5522 10 күн бұрын

Honestly quite incredible

@ryanbartlett672 24 күн бұрын

Great work. Thanks

@CompilerHack 27 күн бұрын

you make the best videos!

@tobyconner5827 25 күн бұрын

you should do a longer video about joke algorithms (especially more obscure ones like hanoi sort), theyre very fun

@fuschia-draws 16 күн бұрын

each algorithm has a little icon !? very cute i love it

@RT777 5 күн бұрын

Minor typo - 1:05:15 says O(nlgon) instead of O(nlogn) in the magenta rectangle

@circuitcraft2399 26 күн бұрын

1. Quicksort can include smarter pivot-selection techniques to guarantee O(n*log(n)) time in the worst case. 2. Shellsort can be O(n*log(n)^2) if you choose the sequence of gaps more carefully. Additional details in replies.

@circuitcraft2399 26 күн бұрын

Explanation for 1: there is an algorithm called "median of medians." It is an O(n) algorithm that finds some value in the list that is greater than (or equal to) at least 30% of the others in the list, and also less than (or equal to) another 30% of them. By using it to choose pivots, we will always shrink the list by a constant factor on each step, guaranteeing logarithmically-many recursive steps.

@circuitcraft2399 26 күн бұрын

Explanation for 2: if we choose the sequence of 3-smooth numbers, we never swap an element more than once on a given iteration. Since there are O(log(n)^2) 3-smooth numbers less than n, we perform that many linear-time iterations.

@ashes6816 27 күн бұрын

this is so good

@LeoStaley 27 күн бұрын

Are there different considerations based on properties of the data, like numerous peices of data with the same values? In such a data set is there anything of note happening when a secondary sort method is used? (Like sorting files by album title, and secondarily by name, or track number? What about if the data is already partly sorted instead of random?

@Kuvina 27 күн бұрын

That's where adaptive algorithms come in, which are covered in part 3 !

@NXTangl 27 күн бұрын

For "A-then-B" you can just sort by A but break ties by B, or you can sort by B, then stable sort by A, or you can use a recursive procedure more like MSD radix sort.

@LeoStaley 27 күн бұрын

@@NXTangl does anybody know how windows explorer does it?

@NXTangl 25 күн бұрын

@@LeoStaley Probably stable sort.

@HesterClapp 26 күн бұрын

I think I saw somewhere that the time complexity of Shell sort is O(n (log n)^2), which is roughly n^1.2, but I couldn't tell you why that's the time complexity

@Kettwiesel25 20 күн бұрын

O(n log^2 n) is a smaller time complexity than n^1.2 or even n^1.00001

@ShowMe7. 27 күн бұрын

yay new kuvina video :3

@proton.. 27 күн бұрын

as pictures

@Living_Murphys_Law 26 күн бұрын

as pictures

@not_estains 23 күн бұрын

radix sort is so cool

@Vaaaaadim 26 күн бұрын

I'm only at the start of the video right now, but I just want to note that ska sort doesn't seem to be included.

@vincehomoki1612 23 күн бұрын

1:05:13 Typo! "and building it is O(nlgon)"

@Kuvina 23 күн бұрын

I'm impressed by how many people have noticed that. But I guess it shows people are really paying attention to the video!

@AshLikes2analyse 26 күн бұрын

You're the best

@eskaigarcia 3 күн бұрын

Wow, just wow

@andriypredmyrskyy7791 26 күн бұрын

Fun fact, Bill Gates published a really neat paper on pancake sort! I wish I was smart enough to understand it. I'd watch a video of someone explaining that paper online.

@not_estains 13 күн бұрын

now explain every shuffling algorithm

@stefanbergung5514 22 күн бұрын

Wasn't there an algorithm that can solve any NP-problem in its minimal time complexity by random generating algorithms and checking if there answer is correct? It's just generliced bogo-sort, but would have been worth a mention.

@mathguy37 24 күн бұрын

cool now i can watch this when binging it the 581st time

@meem2Greene-ju3cs 25 күн бұрын

Fireship ahh video lawful evil ending

@taureon_ 25 күн бұрын

identity crisis sort should randomly start off with quick or merge

@surters 23 күн бұрын

OMGZ block sort!!!

@MessyMasyn 23 күн бұрын

Can't wait to get hired at Google/Facebook/Papa Johns

@BoBoN4Uto 23 күн бұрын

marvel moieverse been real quiet since this dropped

@SysFan808 23 күн бұрын

1:05:16 nlgon

@kvanctok9234 25 күн бұрын

1:05:14 O(nlgon)

@WendidIask 23 күн бұрын

Top sort is not obscure :(. It is used in every DAG problem basically.

@GermanZindro 4 күн бұрын

Already a major mistake at only two and a half minutes. And the runtime complexity of selection sort isn’t even difficult to calculate.

@RileyMyers-zz3je 27 күн бұрын

woohoo!

@BFUS_official 25 күн бұрын

I keep hearing login

@hamzamotara4304 19 күн бұрын

Grade 12 math was not enough for this video XD

@lilyyy411 26 күн бұрын

among

@VladVideos0 21 күн бұрын

Its 117.55 minutes long

@user-jp7zr9gr3n 21 күн бұрын

Не души, Владос

@zoeymccann124 23 күн бұрын

Didn't even mention worstsort 0/10

@rodrigoqteixeira 27 күн бұрын

Yooooooooo.

@thermitty_qxr5276 15 күн бұрын

Hey great video you put effort into, but I got some small problems about your intro jingle It doesn't sound pleasant since there is too much tension which isn't resolved nicely meaning it sounds like it's not done and unsatisfaction. (I assume the first note is the home note or the note that sounds at rest). I may be wrong, and that is supposed to be like that because of the message you're supposed to show. But if not, I can help make a better one because I understand some music theory and I'm a newbie. Thanks for reading