Visualization of Quick sort (HD)

No video

Visualization of Quick sort (HD)

Рет қаралды 852,589

Күн бұрын

An animated demonstration of sorting algorithms.
Read about my new book, "Zuto: The Adventures of a Computer Virus", www.zutopedia.com, or visit my homepage, www.udiprod.com/
This video shows two comparison based sorting algorithms: Bubble sort and Quick sort.
The algorithms are demonstrated by robots sorting balls by hue. Comparison based sorting algorithms must make decisions based solely on pairwise comparison results. This is visualized by the robot's short-sightedness, which forces them to perform pairwise comparisons in a very pronounced manner.
The video culminates in a contest. Each algorithm is presented with an identical series of balls and they compete to see which finishes the sorting task faster. In addition to raw speed, the number of comparisons they perform is also measured.
Advanced viewers will notice bubble sort performs comparisons quicker than quick sort. This is because quick sort has to move around a lot between comparisons. Quick sort aims at reducing the number of comparisons, but in domains where movement is costly, it becomes inferior to other algorithms, which aim to reduce movement as well.

Пікірлер: 556

@ninthpayloader0465 5 жыл бұрын

Bubble sort is so short sighted he didn’t even see that he lost

@larrykelly8508 4 жыл бұрын

He doesn’t have ears

@Muhammad-sx7wr 3 жыл бұрын

He might be deaf, he might be blind, but he sure as heck ain't dumb.

@cosmq 2 жыл бұрын

pure gold comment 😂😂😂😂😂

@ChrisSparks-zp8ue 3 ай бұрын

I think if quick sorting loss they won’t know either

@Johnny_Franco-12_Scratch Ай бұрын

That’s… actually true.

@BioHzrd0010 6 жыл бұрын

I like how after it announces that quick sort won, it just lets bubble sort slowly and pitifully complete its sort.

@razerage1 7 жыл бұрын

bubble sort be like "I hate my life"

@krzywy8873 6 жыл бұрын

@taiyihanle 5 жыл бұрын

Bubble Sort be like "I'm doing my job! ^o^ you go here, you go there... and there you go!"

@cboom3205 5 жыл бұрын

Bruh this is me at me job watching everyone leave as i stay behind to close T_T

@magicstix0r 5 жыл бұрын

And we hate bubble sort's life too...

@aemiil5743 4 жыл бұрын

bogo: hand me the gun

@ImmacHn 11 жыл бұрын

Bubble sort will always have a special place in my heart :')

@smortboi2374 2 жыл бұрын

When u necropost BP

@ImmacHn 2 жыл бұрын

@@smortboi2374 nani?

@multiply67 2 жыл бұрын

@@ImmacHn you're a man

@CrittingOut Жыл бұрын

me too

@brainboy53 Жыл бұрын

I like that quicksort isn’t annoying bubble sort and letting him just do his thing. Such a nice guy

@hendroyohanes4295 5 жыл бұрын

The moral here is to never give up even when you lose

@reda29100 5 жыл бұрын

But you never lose if the match never ends!

@MeistrosLabor 4 жыл бұрын

The bubble Sort Robot still came to a final Solution even if it took years :) its becauz he didnt gave up

@trenvert123 3 жыл бұрын

Trump

@uwu.-.5873 2 жыл бұрын

Bubble sort is me 😔

@scoutintime Жыл бұрын

the moral here is that bubble sort fucking sucks lmao

@ziskador 8 жыл бұрын

omg i felt so sorry for bubble sort robot at the end :(

@marquizzo 8 жыл бұрын

+ziska dor Lights are out, everybody's cleared out of their seats and gone home. The janitor is about to ask him to hurry up so he can clean the floor.

@ziskador 8 жыл бұрын

+marquizzo so sad :(

@ProducShuns 8 жыл бұрын

+marquizzo He says nothing. Keeps on sorting. Janitor mops around him. Doors open the next day. The celebration finally sounds as he clicks in his last comparison.

@frtard 7 жыл бұрын

I felt sorry for it the entire time. Just think about how many balls he had so close to his face...

@Luffi98 7 жыл бұрын

imagin bogo sort robot :(

@granceroblast 10 жыл бұрын

This has to be the best educational video on sorting I have ever seen!

@luisandre2750 5 жыл бұрын

I thought this too. It is amazing seeing how even when you code using comparisons (using if/for/switch) you could have the same output using a more developed algorithm much more quickly.

@randomman7407 5 жыл бұрын

Hungarian dance sorting is much better Check it out!

@mathguy37 10 ай бұрын

9 years later we got better

@NachitenRemix 9 ай бұрын

@@luisandre2750i dont understand what u say lmfao, yes computers use if and? That takes some time, its not literally instantanious, it never is, thats why you need optimization and that is what this sorting algorithm does

@sharpnova2 4 жыл бұрын

bubble sort: what is my purpose? me: to sort in O(n^2) bubble sort: omg

@mate_on_f7916 4 жыл бұрын

Yes

@Muhammad-sx7wr 3 жыл бұрын

Bubble sort be like, "I thought bigger was always better."

@musicexams5258 2 жыл бұрын

Insertion sort intensifies

@slowmotion2300 Ай бұрын

I thought bubble sort would do 10^2 comparisons

@bitonic589 7 күн бұрын

@@slowmotion2300Bro thought bubble sort had constant complexity 💀💀💀

@TomTom-gy7ov 7 жыл бұрын

Legend has it that the bubble sort robot is still sorting

@DirkIronside 7 жыл бұрын

Now imagine if it was a Bogosort robot!

@Anohaxer 7 жыл бұрын

ORST is the alphabetically sorthed correct order

@Anohaxer 7 жыл бұрын

By going: Quick Sort Pivot: R S>R = S to the right (Memory) | [S]O T T>R = T to The right | [S]O T S

@paulcasanova1909 7 жыл бұрын

Tom Tom That would be the Bogo sort bro

@Anohaxer 7 жыл бұрын

Lets just do merger sort then SORT = 19-15-18-20 [19][15][18][20] 19>15 [15-19][18][20] 18

@realeques 10 жыл бұрын

so awesome , we spent 45 minutes in college for what we could have learned through this video

@Muhammad-sx7wr 3 жыл бұрын

Interestingly I discovered bubble sort without being taught it. Only later finding out what it was called.

@MikehMike01 3 жыл бұрын

@@Muhammad-sx7wr most people could come up with bubble sort, insertion sort, or selection sort on their own

@Muhammad-sx7wr 3 жыл бұрын

@@MikehMike01 Things just seemed a bit harder in the 90s and Google was not as reliable. I know however that most people can make these discoveries on their own. I'm just reminiscing with these people how great it felt and yet how far from the mark we were.

@neolord50pro77 10 ай бұрын

@@MikehMike01and to discover things like quicksort or heapsort only through intuition it would require to be an astute mathematician I think.

@MikehMike01 10 ай бұрын

@@Muhammad-sx7wr those three are the O(n²) algorithms which aren’t very good but are easily understood

@legendgames128 2 жыл бұрын

Making computers look cute while also teaching a great concept in a lot of web development? Win-win! Also, noting how the computers are short-sighted is a very good way of describing how computers actually do operations.

@udiprod 11 жыл бұрын

Thanks! Currently I'm busy with two other videos (coming up soon), but I appreciate the interest in more sorting videos. I hope to get around to it soon.

@thatalbeeguy 4 жыл бұрын

KZfaq in 2012: Oh, look at him, he is learning algorithms! I should recommend it to him some time later. KZfaq in 2020: eah! This just the right time!

@figoprovenza9513 2 жыл бұрын

Someone has to do an edit of this video with the "The Rock stare" everytime the announcer say balls

@moogyboy6 5 жыл бұрын

Those have got to be the cutest robots I've ever seen. Look at 'em sort!

@Pigeoncraft 9 жыл бұрын

What about a bogo sort :P

@derekmallory985 9 жыл бұрын

***** ... or the next level : 3 "Bogobogosort is an algorithm that was designed not to succeed before the heat death of the universe on any sizable list. It works by implementing the bogosort on the first two elements in the list. If they are in order, then it bogosorts the first three elements, and so on, increasing by one until the entire list is sorted. Should the list not be in order at any point, the sort starts over with the first two elements."

@v000000000000v 9 жыл бұрын

Derek Mallory there's always a chance that it will sucessfully sort tho!!

@ScipiPurr 7 жыл бұрын

Don't forget the king of all inefficient sorts: Worstsort.

@Anohaxer 7 жыл бұрын

yeah? well in a comment above im trying to bogo sort the word "sort" alphabetically. I do it in batches of 10, random data gotten from www.superkids.com/aweb/tools/words/scramble/ and now going to my 4th batch

@Anohaxer 7 жыл бұрын

kzfaq.info/get/bejne/l76IirurmtiqZmg.html&lc=z12xy3dixtf2tn5cg223yfyzxkqdztugn04.1498860895564993 BOGO SORT BRIEF EXPLANATION AND 49-TRY EXAMPLE WITH 4 INTEGER (CHARACTER) VALUES

@UntakenNick 10 жыл бұрын

When I grow up I want to be a sorting robot..

@markhesse4510 6 жыл бұрын

Quicksort or Bubblesort or Bogosort?

@manuelsputnik 4 жыл бұрын

How inspirational.

@devrafed 4 жыл бұрын

Are you a grown up now? What are you doing now?

@SkoczekPrRO 4 жыл бұрын

@@devrafed he is sorting parcel in postoffice so he is not exactly the robot but some kind.

@Muhammad-sx7wr 3 жыл бұрын

You need to sort yourself out first.

@kenji4861 7 жыл бұрын

Great video. Kids nowadays have so much good resource

@katlicks 3 жыл бұрын

I never knew how Quick Sort managed to have confidence in it's placement without going to the ends first. That cleared it up really easily.

@angelsalvadorcruz7484 11 ай бұрын

this is the cutest video i have ever seen in my entire life, after watching so many boring videos trying to explain quick sort, this is a very welcomed treat

@galzigler 7 жыл бұрын

You should make a visualization for all existing sorting algorithm. Your videos are really helpful, and the best that could be find online to explain how the sorts work.

@traso56 6 жыл бұрын

different but there you go kzfaq.info/get/bejne/obaCdJOIltGpc5s.html

@solomonprenevost4699 5 жыл бұрын

Gravity sort

@anonymoususer9837 4 жыл бұрын

First off, curse you for having a right-to-left-language username, because replying to those screws up your left-to-right typing if you include it. Second, there are way too many sorting algorithms to explain. Many of them are hybrids (like Timsort), many don't work on these colored balls (like Radix Sort), and many are esoteric (not intended to be actually useful, like Bogosort and Slowsort). That and some of them are just *weird* (like Gravity Sort).

@Chr0nic1er 7 жыл бұрын

I am pleased at how accurate the video is. It didn't just count comparisons only, but moved the robots according to performed actions (cycles as it were).

@benmoreaucohen 2 жыл бұрын

Dude I mean why or how, this videos are so old and they are so cool, the quality is genuinely amazing, I love your videos and the educational content they bring, make more!

@kirishanth1585 Жыл бұрын

Props to bubble sort for never giving up. A true inspiration!

@confused6526 8 жыл бұрын

udipod, I just accidentally ran into your video. They're all great. You don't mind telling me what tool/software your used to create the animation? Or your write it yourself? Thanks John N.

@udiprod 8 жыл бұрын

+confused Thanks :) I'm using a tool called Autodesk Maya. It's very powerful but not easy to learn.

@confused6526 8 жыл бұрын

+udiprod ! Thanks a lot for the info. You're done a great job of explaining computer/physics concepts. Keep up with good works. Can't wait to see more of your videos. Have a nice day! John N.

@zork34 5 жыл бұрын

you don't have to write comments like letters

@SiddharthJogi 5 жыл бұрын

@@zork34 😂😂lmao right

@uknownada 5 жыл бұрын

@@zork34 Although it's probably the easiest way to get a reply from a channel like this.

@thowaway24767 9 жыл бұрын

Why don't you give the robot glasses?😊

@TheTurtle-ui4ou 7 жыл бұрын

Well, it wouldn't have vision problems anymore, now would it?

@winandfx 6 жыл бұрын

Yeah, Glasses Bubble Sort is the fastest. Scientists should invent it.

@sonicfire9000 6 жыл бұрын

I see what you did there...

@youtubeismycity 5 жыл бұрын

@@miksuko omg

@MinecraftLD10 4 жыл бұрын

jeffrey Presley Well who designed their vision sensors so near sighted in the first place? *If your into robotics at all, you’ll get this.*

@nalankadi1654 4 жыл бұрын

Bubble sort's perseverance is truly inspiring.

@MinecraftLD10 4 жыл бұрын

I want to hug bubble robot, he deserves it.

@Shimo8_ Жыл бұрын

This is the only video that explained quick sort in a way I can understand

@udiprod 11 жыл бұрын

It places on the ledge a ball from the left side that is designated to be swapped with a ball from the right side. Usually when two elements are swapped, one of them is placed in a temporary location. What's a bit unusual here, is that the element is placed in a temporary location before selecting the ball it should be swapped with. The reason is that the robot has only one free hand (the other one holds the pivot), and putting the ball on the ledge saves moves later when the swap takes place.

@alexlion0511 3 жыл бұрын

"this robot is short-sighted and can only compare balls when they're right in front of its' eyes"

@davieskamanda6622 10 ай бұрын

This is the best educational video I've ever seen. I think using numbers in place of the balls could make the whole process more clear, for in the competition it is difficult to follow what is going on.

@AsbjornGrandt 10 жыл бұрын

Bubble Sort cheated at the end. It didn't compare the last two...

@udiprod 10 жыл бұрын

It's actually not cheating. Bubble sort has an optimization that if in a certain iteration all the pairs are in order, then it concludes no further iterations are needed. It most likely happens in the one of the final iterations, but with luck it can happen early. If you give bubble sort an already sorted list, it will stop after one iteration. Therefore if bubble sort and quick sort competed over on already sorted list, bubble sort would win.

@AsbjornGrandt 10 жыл бұрын

udiprod I didn't suggest that it should have run an additional iteration. It just never compared the last two balls, before marking them sorted. It checked the second and third, and then assumed the first was in order, marking all three at the same time.

@brands2131 10 жыл бұрын

Asbjørn Grandt That's because all 3 were already sorted. Ok, let me explain, and also to the other people that liked your comment. In the end, we had a section that was already sorted, the balls that were lit up, and a section that was unsorted, the 3 balls at the end. When bubblesort went to sort out the last 3 balls, it compared the first 2, no swap was made, then it compared 2 and 3, and no swap was made. We have bubblesorted the unsorted section, no swaps were made during that iteration, now we can assume that the unsorted section has been sorted (since there were no swaps) this is because an efficient bubblesort has a "swap" flag that is turned on if a swap was made, since we ran through the 3 unsorted balls, without turning on this flag, then bubblesort knows all element in this unsorted section are sorted. You can see this at 3:05 where bubblesort checked all 3 balls in the unsorted section and did not make any swaps, leaving the swap flag down, meaning we can stop the algorithm early.

@AsbjornGrandt 10 жыл бұрын

Brandon Sandoval I can see that now that I rewatched that part

@SimonTiger 4 жыл бұрын

@Asbjørn Grandt Hehe...it's because already knew the list was sorted! How? The last pass it performed was: "Swap 1 2? No. Swap 2 3? No." If it's all no's, all the smaller elements are already on the left, and the bigger ones on the right, meaning that the list is already sorted.

@ahmde 5 жыл бұрын

Just WOW, this visualization is on another level!

@shaner217 11 жыл бұрын

Amazing video. I always thought there should be a visualization program that visualizes computer code algorithm in a nice way like you've done here for these sorting algorithms, it could have a visual that shows how data is being passed around and manipulated in the computer code or perhaps computer networking. Maybe you're the guy who should make them! Thanks again for the awesome vid.

@deanmoncaster 4 жыл бұрын

Even though I knew the outcome before they started I still wanted bubble sort to win. They're so cute!

@billbill8852 4 жыл бұрын

Nearly 1am and KZfaq recommends this out of the blue. And I watch it anyway. Thus is life.

@sapitron 11 жыл бұрын

What a painstaking process should have been to animate that contest. hats off.

@syrilfiggus1350 11 жыл бұрын

Ahhh, so Sorting competitions are going to be what replaces sports when the robots take over. Very informative.

@poliopoptm4474 6 жыл бұрын

boy this new series of battlebots is going great.

@thehammurabichode7994 4 жыл бұрын

"I hurt myself today" - Bubble Sort

@AquaDavie 5 жыл бұрын

The lore behind all these sorting videos I’ve been binge watching

@colossalgamesofficial7947 4 жыл бұрын

Super relaxing

@withbestrequest 7 жыл бұрын

Your visualizations are awesome! This is how educational material should be like!! thnx

@FiendishFatty 2 жыл бұрын

Is it just me or I just binge watch all of these sorting analysis videos

@Quarker 11 жыл бұрын

Yay you let Bubble Sort finish this time! Btw, if you were able to make more videos like this on other sorting algorithms, it'd be extremely helpful!

@channelname10yearsago68 4 жыл бұрын

Don't feel sad for the bubble sorting bot. He's doing his best

@nathanj.williams1955 4 жыл бұрын

More insightful than meets the eye. Tiny training video to algorithms. Cool CGI.

@anikkhan8811 3 жыл бұрын

Quick sort made the best comeback in history!

@iagoabreu6986 4 жыл бұрын

The year is 2020 and the bubble bot is still sorting the balls

@valied8131 6 жыл бұрын

This is the quality aesthetic i signed up for.

@zapole 7 жыл бұрын

I remember when I learned Java and my teacher expected us to do plan and program such a thing like "bubble sort", but we did it with buckets as long as I remember :)

@yiwen6794 5 жыл бұрын

Who watched till the end? That bubble sort deserves some attention

@Quent1500 4 жыл бұрын

Thx, you saved my engineering diploma.

@Broockle 7 жыл бұрын

These are fun to watch. Though I think all these approaches could all be explained in a single video. That would be nicer than having to watch all these Separate Great job making this random subject engaging though :D

@Densmoreb1 2 жыл бұрын

The robot is not the only one that needs balls close to its eyes

@SyuAsyou 7 жыл бұрын

泡沫排序法：找到最亮的球，然後排到最亮的位置；接著找到次高的球，然後排到次亮的位置。重複以上步驟直到排完最暗的球。快速排序法：隨機選出一個球當作基準，然後比較每一顆球，比基準亮的球移到亮邊，比基準暗的球移到暗邊，最後的空位就是基準的位置。排完後排列被分成兩個較小的排列，分別對較小的排列重複以上步驟直到排完。

@Dadax9398 5 жыл бұрын

@antony_303 Жыл бұрын

Now i want a version where every time the narrator says "balls" a Vine Boom sound plays

@robbierotten2215 7 жыл бұрын

Winner! Bubblesort is like, I don't give a crap, gotta finnish this s_t.

@Clement-xy9iv 6 жыл бұрын

Nice explanation!

@ricksminecraft 5 жыл бұрын

Wow! Excellent Visualization. Cool.

@nicflatterie7772 5 жыл бұрын

Wow, I wish I had this sort of video when I was in CS in college. Great work, great channel!

@EgorBo 5 жыл бұрын

Give those robots already sorted data and we will see who is better ;-)

@asj3419 8 жыл бұрын

9_in 11_order. 4_the 6_of 8_sentence 3_sort 5_words 1_Hello, 7_this 2_please 10_acending

@themandel2017 6 жыл бұрын

Hello please sort this sentence in ascending order.

@anonymoususer9837 6 жыл бұрын

Counting sort 😀

@k_tess 6 жыл бұрын

I think you gave me OCD.

@groszak1 6 жыл бұрын

I'll start with a swap 8_sentence 11_order. 4_the 6_of 9_in 3_sort 5_words 1_Hello, 7_this 2_please 10_acending

@QuartzOfficial 6 жыл бұрын

Hello, please sort the words of this sentence in ascending order

@SarenArterius 10 жыл бұрын

radix sort pls

@anonymoususer9837 4 жыл бұрын

Radix is very powerful, beating even quicksort and mergesort if the keys in the sequence are short enough, but it takes a lot of memory, stinks on longer keys, and only works on numbers (so no colored ball sorting). If you want to go all the way, counting sort is even faster than radix in an optimal set of elements, but it only works on positive integers (similar to radix but it can't even hypothetically handle decimals), takes even more memory than radix (as much memory as the biggest element), and is even slower if the biggest element is too big (even if the other elements are smaller).

@krisizcelja 4 жыл бұрын

I want to see the base 10 one. You know, the ear rape one?

@toddkes5890 4 жыл бұрын

@@anonymoususer9837 Ball colors can be expressed in 'brightness'. For example, the above spheres can be '000000' for the pitch black one, and 'FFFFFF' for the brightest one. From there, Radix can sort the balls

@pa20065 10 ай бұрын

The BubbleSort guy is smarter: he lets the other guy win, so he isn't bothered with these stupid tasks anymore!

@Adomas_B 4 жыл бұрын

Bogosort is also a very great sort, it can sort completely randomised stack in one move! If you're astronomically lucky

@martinbalage9225 4 жыл бұрын

“The End. Thank you for watching” before bubble sort taking a break...funny, and cruel.

@user-fi5sx2op8x 4 жыл бұрын

The first algorithm is more likely selection sort than bubble sort

@teaguejelinek4038 4 жыл бұрын

I think bubble was just a little nervous. With a name like quick sort as the opponent I would have been too. Good job both of u

@GretgorPooper 7 жыл бұрын

This is an adorable way to explain algorithms to kids

@dicidicee 10 жыл бұрын

Very original and well done !

@valrabellkeys9867 5 жыл бұрын

Great video, explains the algorithm quite well!

@pga128 9 жыл бұрын

This channel is quality.

@shanshansan 3 жыл бұрын

Comparing bubble sort and quick sort together is like a snake to an alligator fight

@TheRojo387 Жыл бұрын

One pass of Bubble Sort can still be useful for simulations involving raytracing. What else can it be used for? I invite replies of your answers.

@ciCCapROSTi 5 жыл бұрын

Eh, problem is the robot's movement takes time, which is not true when sorting something with random access. Somewhat comes back when you think about cache misses, but still. The memory itself is random access.

@MemeManDan20 4 жыл бұрын

Would love to see a video on bogo sort

@OddworldCrash 11 жыл бұрын

I'm learning this for Visual Basic and i was very moody till i saw this video. Awesomely made :D

@user-kufihfmurb Жыл бұрын

Bogo sort represents:"eternity" Stooge sort represents:"shorter than eternity" Bubble sort represents:"patience" Quick sort represents"HURRY UP"

@mrpowershell6900 5 жыл бұрын

I was watching historical youtube video's on how WWI started and ended here. Quick sort wins.

@dude_ranvier 5 жыл бұрын

Great video and animation

@Hao-gc3dp 11 жыл бұрын

Awesome animations! Hoping you could make videos on other sorting algorithms.

@CraftySquid-io8ih 2 жыл бұрын

This video almost caused me to break out laughing in my Java class. Very informative and is great at describing how the algorithms work and how efficient they are but why did that have to sort Balls.

@gavincurtis 4 жыл бұрын

If you overclocked Bubble’s reduced instruction set, he could win.

@linsproul3548 6 жыл бұрын

so this is how robots keep themselves entertained

@marinadavies1917 5 жыл бұрын

Please do more of these

@seaque. 4 жыл бұрын

Never give up king

@RaymanChrome 4 жыл бұрын

What about Cocktail Shaker Sort?

@metacross2826 5 жыл бұрын

Bubble sort robot is doing his best

@metacross2826 3 жыл бұрын

Hello, old me

@toxic_narcissist 4 жыл бұрын

This deserves 500M, not 500k views

@groszak1 6 жыл бұрын

There are several different pivot rules for quick sort, such as random pivot you used, first pivot, last pivot, middle pivot and median of three (median of first, middle and last pivot).

@CoryMck 6 жыл бұрын

Cool, but is it fair to include the time of the robots traveling since in reality the code/sorting algorithm would not require the robots to move and they would essentially be at the same place solely depending on how many comparisons they had made.

@udiprod 6 жыл бұрын

Sorting algorithms performance can be evaulated according to several criteria. Comparisons may be the most important one, but there are others, e.g., swaps (memory writes). Also, if the algorithm moves around a lot it can impact performance, since a computer's memory is usually optimized for speed assuming the program accesses close locations. If it jumps around it becomes slower (this is only true if the sorted list is really big). Anyway, the video mainly focuses on comparisons, like you say. The robot moving slows them down a bit, but doesn't effect the end result.