The main advantages of heap sort are that it sorts elements in place and produces a valid partial result while the algorithm is still running. With most other algorithms you don't get any results until they're finished or nearly finished. For instance merge sort produces no results until the start of the final merge. Heap sort starts producing results right after heapify is done, albeit in reverse order. Another advantage is that heap sort doesn't require a lot of metadata. With merge sort you must keep track of all the lists to be merged, typically using a stack. With heap sort you just need a reference to the element being sifted up or down. The sift operations use tail recursion, which means they can be done iteratively. It's not really fair to compare heap and merge with only ten elements. Try it with about 10,000 and see how they compare.
"reverse order" In a order. Not 'reverse order'. The order it produces results in may or may not be the correct 'side' of the sort. It depends on if it's told to sort ascending or descending. Even then, it can invert your choice and then return the list backwards to you when you ask for it.
I find a heap most useful specifically in pathfinding. Don't actually sort it, just maintain the heap properties when all you really need to know is what is the biggest (or in some cases smallest) out of a collection, like when selecting which node to expand next. You don't care about how the rest of the list is sorted, as long as you van get the biggest one. You can get it in one operation, then run a sift-up one time, which will take something like square root of N operations...
Well, Wikipedia isn't supposed to explain stuff for better understanding, it's supposed to just provide the information for everyone. That's why these tutorial-like videos are so important.
Heap Sort may not be ideal when sorting is all you want to do, but this whole idea of a heap becomes invaluable when you need a data structure that allows you to always take out the smallest element quickly, but also be able to quickly modify the data in the heap in between. And often in solving some more advanced problem this is exactly what you need to do it efficiently.
Maks Rosebuster Heapsort only requires one array to be used, so it doesn't take up as much memory as mergesort. Even with an array of a million objects, heapsort only takes about a second to sort everything. (I know because I just had to write a heapsort algorithm for a university project and the I remember hearing that the professor wanted us to sort that large of an array in under 30 seconds.)
Yeah, in that implementation, it’s often called a priority queue, because you can freely insert objects, and easily look at and remove the one with highest priority (imagine a hospital waiting room, where the people with worse injuries get taken in first).
00:07 Intro to Heap/Heap Sort 02:37 Building the Heap in the first place (Heapify) 03:33 How is new elements added into a Heap 04:07 Heap Sort V.S Merge Sort Excellent Work! I felt like I haven't grown up yet! lol
As an A-Level Computer Science student, I agree CodenameLambda (HL3 confirmed?). It is a lot easier to understand an algorithm when you have a visualization of what it's doing.
Different sorting compilations started showing up in my recommended, and I started watching them, confused on what they were, and now these have shown up. I’m not disappointed, just confused.
groszak1 actually a fairly simple digital logic circuit can be made to sort/compare several (less than 10) objects at once. An entirely new set of sorting algorithms would need to be implemented to take advantage of this but I wouldn't be surprised if you could get an order of magnitude improvement in sorting speed over a lucky quicksort. The problem with doing this is that sorting isn't done very often. You may ask your computer to sort things occasionally but it's not happening 60 times a second, once for each frame/update in a video game for example so doesn't need a drastic speed up.
I felt sorry for the Heap Sort robot still working hard while the Merge Sort robot was just standing there. I imagine merge sort robot tapping his foot impatiently!
I just came from the halting problem video, amazed how great your physical world analogies are. The short-sighted robot that can only look closely at two balls at a time in order to compare them is another gem!
Rohan Zener Radix sort sorts the number by the following procedure: First it sorts the elements based on units place Next it sorts the elements based on tens place And so on...
I created both algorithms to test the time it takes for each to sort a vector, and actually heapSort was actually faster than MergeSort... like twice as fast. I think that making copys of the initial vector is a heavy task and makes HeapSort better or something I don't know, but numbers are really consistent
Which animation seem faster to you? They're all the same. If you ask about merge sort vs heap sort then you can check the comparisons count. They advance at a similar rate.
I remember watching visual versions of these (the ones that make sound that sounds like if edm music made an incest baby with a 4 year old 'composing' music) and being so confused about what was going on, and your videos make things so much easier to understand. Thank you for making these, keep up the good work!
Quick sort could be good Take a book from the middle, and put every book that comes before that before it, and every book that comes after that after it. Repeat it with your groups, until you have groups so small, they could be sorted with a different sort.
this video makes the concept of heapsort so obvious. honestly, i don't know why I was even wasting my time trying to decipher that thick, confusing textbook anymore.
One major advantage to heapsort that's not addressed here. If you have more elements to sort than will fit into memory, you need to resort to an external merge sort. And the number of passes that the merge sort requires is dependent upon the number of runs (sorted sequences) that are already created. Assuming you can store N items in memory, the technique is to read in N items, sort them, then write out that run and repeat until you've created the initial set of runs. So each run is N items long. However, in heapsort, you read in N items, write out the lowest item and then read in the next item. If it's greater than the item just written, place the newly read item into the heap and continue. If it's less than the item just written, reduce the heap by 1 element and save the newly read item into storage. Result is that on average, using heapsort, the initial length of each run is 2N, not N. So you have about half as many runs to process with mergesort. So it runs faster.
I think it would be more fair to also show a heapsort vs mergesort when the heapsort already has a heap structure. Both of these algorithms have O(n log n) time complexity, assuming the heapsort is executing on an already existing heap. Heaps have the advantage that extracting the min (or max for a maxheap) element is a consistent O(log n) time complexity, which is fantastic speed. This has a very high amount of use cases.
…is it weird I wish I had the money to commission this channel to animate explanations of more and more sorts in this style? The graphics remind me of the old Kutoka Interactive edutainment games I used to play as a kid, like Mia Mouse. It feels like I’m hear to learn without judgement, and yet with little bits of humor thrown in. Not to mention all the sounds are soothing.
I love these videos, but I wish youtube had recommended them to me two years ago when I was taking structure and algorithms class.... but is good to remember now, since I forgot it all
great video, i enjoy the robot animations, esp the battle at the end to help actualize sorting algorithms. Helps some of us visual-programmers understand what's going on. I get sick of algorithms easily, this helps :)
I think u should put numbers that represent the brightness on the ball, because numbers will help very much in illustrating as well as understanding the algorithms
Nice ... I have learnt Quick Sort and Heap Sort for 2 years and used it to solve many exercises in my school but in that time, I just learnt by heart (because I can't understand them) Until now, I can understand these algorithms ... thank you so much !!! Love you :* =))) ...... And the robots are so cute :v =)))
How can you learn these algorithms without understanding what they do? You memorize the code or something? Like the exact things you have to type? I think when most people program something, they know what they want the program to do and then they construct the code doing exactly that.
Great video. This gave me a great review of heaps. Just out of curiosity when animating the robots do you do all the movements individually or do you have a way of automating it?
***** Thanks for the suggestion. I think visualizing selection sort using robots sorting would like quite similar to bubble sort, which I already had done. Bubble sort makes more swaps, but the basic idea of searching for the min (or max) in the unsorted part of the list would look very similar.
Maybe it's for the better that you don't put your dirty little hands on gravity sort. Clearly if you need a video to understand it, it's not meant for you. Stick to bubble sort, peon.
I found some demonstrations regarding an algorithm called "gravity sort" but I can't seem to find any video that gives an explanation. Would you be able to point me in the direction of some resources that could explain it?
Could you please specify the decision tree which is being used in heapify? I can't figure out from how the order of which ball to look at next is being determined. And when you say the lowest ball do you mean the one at the bottom or the darkest one?
The next video will be about physics again, and will be published quite soon hopefully. I promise to do another sorting video afterwards. Thanks for the suggestion. May I ask why you are particularly interested in bogosort?
I would like to see a comparison between Bubble Sort and Gnome Sort. BTW: When I programm something to use gnome sort, I add a variable, at which number the algorithm was, when it starts to compare to the start. Then, when it's ready, it can go just to this index and don't compare up to the turning point.
Iirc heap sort is like this: Suppose we have an array of data, from 0x0000 to 0xFFFF, each value is represented by one and only one datum. Separate the data into heaps of size 0x100, i.e. 0x0000 to 0x00FF; 0x0100 to 0x01FF; 0x0200 to 0x02FF, etc. Check to see that all data is placed into their heaps; then assign a heap number to each heap. Now one heap can be treated as a single datum, i.e. heaps 0x0 to 0x100. Sort the heaps using another technique, like QuickSort. Now the data is nearly sorted, use multithreading to sort multiple heaps at once. Here I'll use QuickSort again. Since the heaps are sorted, i.e. the largest element in the last heap is no larger than the smallest element in the next, we need not check if the entire array is in order after we sort each heap, for it is by definition always true after we sort each heap separately In this sample size of 65536, we only need to compare the whole array against a number once, which is faster than the method shown
The "click here" parts in the video didn't work for me. The only thing that happened was it paused and restarted the video. Can you put links to the other videos in the description?
It would be interesting to "hand trace" a small manageable example like this and count the number of swaps using the traditional method (of just "popping" the top element), vs. my idea of popping the top 2 elements (the root and the brighter of the children in this example). I am thinking if the number of swaps is less using my method, it is a valid improvement and should make runtime on a more substantial tree (such as 1 million random numbers), get sorted faster with "double pop" heapsort. The idea is to get the known 2 brightest balls out of the heap quicker (than 1 at a time).
5 ปีที่แล้ว
why at 1:20 black ball didnt spaw with left again ?
It swaps with the brighter of the two, and the right one is a bit brighter. Swapping with the brighter one makes sure the new parent will be brighter than both its children.
These type of sorts are mainly for educational purposes only since counting sort seems to be very fast for a reasonable number of possible values and is much simpler to implement. I tried implementing heapsort but I got myself into a heap of trouble.
I don't think this would be a really good idea (since the algorithm is just too difficult to understand), but Tim sort looks like a really popular algorithm nowadays (Python and Open JDK implement it). There's also some stupid algorithms like Slowsort or one I implemented called "Permutation sort", which checks every single permutation of the array until it finds the ordered one. Anyway, I really like how easy to understand are your videos!
Hey, why don't you have a return to bubble sort and have selection sort? And then maybe after that, insertion sort. Then shell sort or comb sort with the faster ones.
I might. It's an interesting algorithm. It would have to look very different than the current way I visualize sorting algorithms, since radix sort relies on digits of numbers, so sorting by colors won't work well.
This video distorts the value of Heap Sort: Heaps/Heap sort is nice when you have big sets (of colored marbles). And when marbles are added (This keeps previous sorted 'info', without the need for new comparisons/recalculations)
Marksman560 You are talking about heaps in general. Heap-sort is a sorting algorithm that uses a heap, but it can't handle new marbles. It has to restart sorting from scratch. Btw, I did mention heap sort has some benefits in the accompanying link zutopedia.com/hs_vs_ms.html And you are right, perhaps it's worth a mention that heaps by themselves have some great benefits of their own.
Wait a minute. Since Heap sort relies on the fact that the element is sorted from lightest to darkest, couldn't it theoretically faster than merge-sort? As the heapify process is actually sorting from darkest to lightest but in reverse.
![Visualization of Einstein's special relativity [HD]](http://i.ytimg.com/vi/CS7aLVHpeTs/mqdefault.jpg)
![Visualization of Einstein's special relativity [HD]](/img/tr.png)
The main advantages of heap sort are that it sorts elements in place and produces a valid partial result while the algorithm is still running. With most other algorithms you don't get any results until they're finished or nearly finished. For instance merge sort produces no results until the start of the final merge. Heap sort starts producing results right after heapify is done, albeit in reverse order.
Another advantage is that heap sort doesn't require a lot of metadata. With merge sort you must keep track of all the lists to be merged, typically using a stack. With heap sort you just need a reference to the element being sifted up or down. The sift operations use tail recursion, which means they can be done iteratively.
It's not really fair to compare heap and merge with only ten elements. Try it with about 10,000 and see how they compare.
There're an inaccuracy in your statement tho. If heap sort is producing results in reverse order, just use min heap.
"reverse order"
In a order. Not 'reverse order'. The order it produces results in may or may not be the correct 'side' of the sort. It depends on if it's told to sort ascending or descending. Even then, it can invert your choice and then return the list backwards to you when you ask for it.
I find a heap most useful specifically in pathfinding. Don't actually sort it, just maintain the heap properties when all you really need to know is what is the biggest (or in some cases smallest) out of a collection, like when selecting which node to expand next.
You don't care about how the rest of the list is sorted, as long as you van get the biggest one. You can get it in one operation, then run a sift-up one time, which will take something like square root of N operations...
@@Tasarran nah it's log n, which is way less than sqrt N
How are they gonna fit that many balls, let alone make time to sort them?
It's fun how theese child-oriented videos actually explain heap implementation better than Wikipedia article. Keep up the good work!
Well, Wikipedia isn't supposed to explain stuff for better understanding, it's supposed to just provide the information for everyone. That's why these tutorial-like videos are so important.
Who said these were for children? These are for college students man!
@The Rino im a kid, and somehow I still understand it.
@@Lauren-ub6mj look at this genius guys
Jason Zhang this is already simplified enough for kids
Heap Sort may not be ideal when sorting is all you want to do, but this whole idea of a heap becomes invaluable when you need a data structure that allows you to always take out the smallest element quickly, but also be able to quickly modify the data in the heap in between. And often in solving some more advanced problem this is exactly what you need to do it efficiently.
Maks Rosebuster Heapsort only requires one array to be used, so it doesn't take up as much memory as mergesort. Even with an array of a million objects, heapsort only takes about a second to sort everything. (I know because I just had to write a heapsort algorithm for a university project and the I remember hearing that the professor wanted us to sort that large of an array in under 30 seconds.)
You gave an explanation of priority queue with implementation, nice
Yeah, in that implementation, it’s often called a priority queue, because you can freely insert objects, and easily look at and remove the one with highest priority (imagine a hospital waiting room, where the people with worse injuries get taken in first).
K1naku5ana3R1ka very interesting
00:07 Intro to Heap/Heap Sort
02:37 Building the Heap in the first place (Heapify)
03:33 How is new elements added into a Heap
04:07 Heap Sort V.S Merge Sort
Excellent Work! I felt like I haven't grown up yet! lol
Thank you, Yuyuko-sama
I really like your videos about sorting. They are great visualized, and it is the first time for me understanding Heap Sort and Quick Sort XD
CodenameLambda Great :) Thanks!
udiprod
Nothing to thank for, because I have to thank you ;)
So: Thank you!
As an A-Level Computer Science student, I agree CodenameLambda (HL3 confirmed?). It is a lot easier to understand an algorithm when you have a visualization of what it's doing.
Heap sort is still my favorite, it's just a beautiful algorithm that works perfectly when you have to sort extremely large lists.
Pigeonhole sort:
@@bitonic589pigeonhole is only good if every element is unique
@@bitonic589 imagine sorting floats with that
@@official-obama Treat the floats as integers
@@official-obamaCounting sort:
Different sorting compilations started showing up in my recommended, and I started watching them, confused on what they were, and now these have shown up. I’m not disappointed, just confused.
"Each ball is brighter than its children."
Looks like those kids need some homeschooling.
That One Random Gamer there’s a lot of corruption in the ball education system- money over mind, it’s a depressing world out there for modern balls
@@zeusrulez Yeah, many balls have been popping themselves with needles. In Memoriam of Bright Maroon-Black.
xD
@@zeusrulez this comment is too underapprechiated
I'm the one dumbass thinking this was an interracial relationships joke
you seriously need to get those robots a set of glasses, then again, it'd prevent them from taking over without them
but then it won't be realistic, computers can't just analyze every item simultaneously
groszak1 actually a fairly simple digital logic circuit can be made to sort/compare several (less than 10) objects at once. An entirely new set of sorting algorithms would need to be implemented to take advantage of this but I wouldn't be surprised if you could get an order of magnitude improvement in sorting speed over a lucky quicksort. The problem with doing this is that sorting isn't done very often. You may ask your computer to sort things occasionally but it's not happening 60 times a second, once for each frame/update in a video game for example so doesn't need a drastic speed up.
groszak1 computers use mostly quick sort
@@groszak1 I believe it was a joke
The robots with glasses sorting algorithm is called radix sort.
I love how the Merge Bot had a face like "Can I leave now?" Or "Can I have my cookie now?"
I felt sorry for the Heap Sort robot still working hard while the Merge Sort robot was just standing there. I imagine merge sort robot tapping his foot impatiently!
@@KristabelHiltonwait till you see the stooge vs bogo video 🤣😭 poor dude stood there for half an hour
I like the screens in front of their table. It makes it much easier to understand.
Bro that burger look like a noob subreddit icon
I just came from the halting problem video, amazed how great your physical world analogies are. The short-sighted robot that can only look closely at two balls at a time in order to compare them is another gem!
I would like to see a Radix sort video.
Rohan Zener kinda like sorting quarters then sorting again and again until it is sorted. idk
Rohan Zener Radix sort sorts the number by the following procedure:
First it sorts the elements based on units place
Next it sorts the elements based on tens place
And so on...
Radix rocks... but not on colored balls. Which I assume was the point.
Radix only works on integers though, so it's not going to fit the colored ball example.
You can just put numbers on the balls, can't you?
It's 1AM I have school tomorrow I need to finish my homework but I'm looking at CGI robots demonstrating sorting algorithms
Large Moose
realy? cgi robots, not real ones?
Pa Pinkelman
Really*
And I meant that the little CGI characters are representative of robots. So... CGI robots.
I know what you meant... I rea ll y do.
Plot twist: the homework IS about sorting algorithms
Hey, my homework is about heap sort, so what’s the problem?
One of the best, visually well explained educational videos my eyes have ever watched.
I have no idea what brought me here but this seems to be a good way to spend my quarantine
This series is a gem
So are these little robots actually in my computer?
yes it is my dude
That's bullshit, but i believe it)
@@cyllum8627 r/wooosh
They are in your blood. They carry your oxygen.
@@guidomarrone9562 **they sort your oxygen
Even before the match started I knew Heap sort would lose :(
It seems like a bad sort
Spoilers, man.
It's better than bubble sort, though.
It has its uses, like when speed is not that important but memory usage is a big concern.
Heap sort is not bad; it's O(nlog(n)) just like Merge sort.
I created both algorithms to test the time it takes for each to sort a vector, and actually heapSort was actually faster than MergeSort... like twice as fast. I think that making copys of the initial vector is a heavy task and makes HeapSort better or something I don't know, but numbers are really consistent
4:14 im just curious if you guys make the animation faster so it does it faster, is that the case?, it doesnt look like it is faster though...
Which animation seem faster to you? They're all the same. If you ask about merge sort vs heap sort then you can check the comparisons count. They advance at a similar rate.
udiprod The yellow one, thanks for the answear
I remember watching visual versions of these (the ones that make sound that sounds like if edm music made an incest baby with a 4 year old 'composing' music) and being so confused about what was going on, and your videos make things so much easier to understand. Thank you for making these, keep up the good work!
Do smoothsort. It's along the same lines as heapsort, but does things kinda backwards so that it doesn't have to move any data if it's already sorted.
It might be more efficient for someone to design better eyes for your robots :P
this is not possible, as they are looking into the souls of the balls
That’s right, skin may be darker but the soul is blacker. (Racism humor intended, no harm intended, im sure i wasnt the only one that thought this.)
DEFCON1GAMRS yeah me too
the good Boyes go at the front,the bad Boyes go to the back
the "short sighted robot" is just an metaphor for the way the algorithms are programmed.
Now this is how all programming tutorials must be made! Excellent! In this way they can be understood by small kids.
I really would like to see more of those videos about sorting. I need to find a quick way to sort my books in alphabetical order.
Quick sort could be good Take a book from the middle, and put every book that comes before that before it, and every book that comes after that after it. Repeat it with your groups, until you have groups so small, they could be sorted with a different sort.
One of the best and simpliest explanations ever.
Not gonna lie, this actually kinda fun to watch.
My teacher is now playing this in the Data Structure lesson! :)
Kinda sad though cause this is actually kind of a poor example of heap sort considering usually it's faster than merge sort
i love seeing the winner robot just sit there waiting like
*can i go home now*
this video makes the concept of heapsort so obvious. honestly, i don't know why I was even wasting my time trying to decipher that thick, confusing textbook anymore.
0:42 "Now the tree is *_in an illegal state."_*
-had me rolling-
One major advantage to heapsort that's not addressed here. If you have more elements to sort than will fit into memory, you need to resort to an external merge sort. And the number of passes that the merge sort requires is dependent upon the number of runs (sorted sequences) that are already created. Assuming you can store N items in memory, the technique is to read in N items, sort them, then write out that run and repeat until you've created the initial set of runs. So each run is N items long. However, in heapsort, you read in N items, write out the lowest item and then read in the next item. If it's greater than the item just written, place the newly read item into the heap and continue. If it's less than the item just written, reduce the heap by 1 element and save the newly read item into storage. Result is that on average, using heapsort, the initial length of each run is 2N, not N. So you have about half as many runs to process with mergesort. So it runs faster.
Thanks!
I Realy Struggled with Heap Sort. So This Helps ALOT.
These animations are delightfully nostalgic
i dont understand why anyone would need this information but its cool and i like it
I think it would be more fair to also show a heapsort vs mergesort when the heapsort already has a heap structure. Both of these algorithms have O(n log n) time complexity, assuming the heapsort is executing on an already existing heap. Heaps have the advantage that extracting the min (or max for a maxheap) element is a consistent O(log n) time complexity, which is fantastic speed. This has a very high amount of use cases.
Your robot animations are adorable!
…is it weird I wish I had the money to commission this channel to animate explanations of more and more sorts in this style?
The graphics remind me of the old Kutoka Interactive edutainment games I used to play as a kid, like Mia Mouse. It feels like I’m hear to learn without judgement, and yet with little bits of humor thrown in. Not to mention all the sounds are soothing.
I love these videos, but I wish youtube had recommended them to me two years ago when I was taking structure and algorithms class.... but is good to remember now, since I forgot it all
I love all of your videos. They are the best! Keep up the good work
great video, i enjoy the robot animations, esp the battle at the end to help actualize sorting algorithms. Helps some of us visual-programmers understand what's going on. I get sick of algorithms easily, this helps :)
I like the fact that I don't fucking know what this channel is for, but still love it
It's all visual analogy for computer coding systems.
I think u should put numbers that represent the brightness on the ball, because numbers will help very much in illustrating as well as understanding the algorithms
heapify: one of my new favorite words
This is an excellent visualization of trees and heap sort. Damn.
The explain is so brief and clear, thanks so much.
I need to see a tournament of every sorting algorithm in this style
Love these videos! Would be great if you could do some more. So much help. Thank you!!
Through this video I understood the concept of heap sort. (I am a informatics student)
I like that you made the ROBOT EYES MOVE, look at each ball when they are brought to the robot’s face. :)
I noticed that. :)
Nice ... I have learnt Quick Sort and Heap Sort for 2 years and used it to solve many exercises in my school but in that time, I just learnt by heart (because I can't understand them)
Until now, I can understand these algorithms ... thank you so much !!! Love you :* =)))
......
And the robots are so cute :v =)))
How can you learn these algorithms without understanding what they do? You memorize the code or something? Like the exact things you have to type? I think when most people program something, they know what they want the program to do and then they construct the code doing exactly that.
always nice to see one of these
I don't know how these sorting algorithm videos could be useful to me someday..
Well, you understand how each sorting algoritm works and which one is better
If you ever get into programing
I never thought I be so into a series about watching two robots see who can sort faster
I think I need to go to bed now...
Great video. This gave me a great review of heaps. Just out of curiosity when animating the robots do you do all the movements individually or do you have a way of automating it?
Thanks! Yes, it's automated using a script.
udiprod
can you do selection sort vs merge sort next?
***** Thanks for the suggestion. I think visualizing selection sort using robots sorting would like quite similar to bubble sort, which I already had done. Bubble sort makes more swaps, but the basic idea of searching for the min (or max) in the unsorted part of the list would look very similar.
try radix LSD then, i love these videos
Can you do a video on gravity/bread sort? I don't understand it at all and I love your visualizations.
sakurawolfie
It just gravitates units, it can't be visualised here.
Gravity Sort just makes the darker ball heavier and vice versa and then pushes them to fall of the shelf
And bread sort just sorts bread not balls
Maybe it's for the better that you don't put your dirty little hands on gravity sort. Clearly if you need a video to understand it, it's not meant for you. Stick to bubble sort, peon.
I found some demonstrations regarding an algorithm called "gravity sort" but I can't seem to find any video that gives an explanation. Would you be able to point me in the direction of some resources that could explain it?
"Now the tree is in an illegal state"
Ok who's been planting trees in israel
😂😂 dafuck
this is great
Other trees
KKL
Now this is genius.
Could you please specify the decision tree which is being used in heapify? I can't figure out from how the order of which ball to look at next is being determined. And when you say the lowest ball do you mean the one at the bottom or the darkest one?
Will you be doing all of the common basic/advanced sorts?
+Pyramid132420 I plan to do more of them, among other things.
The next video will be about physics again, and will be published quite soon hopefully. I promise to do another sorting video afterwards. Thanks for the suggestion. May I ask why you are particularly interested in bogosort?
udiprod I'm actually really interested in the efficiency of bogosort vs bozosort
I would like to see a comparison between Bubble Sort and Gnome Sort.
BTW:
When I programm something to use gnome sort, I add a variable, at which number the algorithm was, when it starts to compare to the start. Then, when it's ready, it can go just to this index and don't compare up to the turning point.
love your videos, please keep doing them :)
Thanks!
These animations are amazing. Thank you!
4:20 why does heap shown with 2 shelves?? doesnt it sort in place??
Welcome to heaps, where no one gets married.
Very interesting video. I cant seem to wrap my head around the heap sorting thing but hey it was fun to try
Oh my!! I love your videos, you need to make more!!!
Dang son whered ya get that no bezel display? 1:49
Iirc heap sort is like this:
Suppose we have an array of data, from 0x0000 to 0xFFFF, each value is represented by one and only one datum.
Separate the data into heaps of size 0x100, i.e. 0x0000 to 0x00FF; 0x0100 to 0x01FF; 0x0200 to 0x02FF, etc.
Check to see that all data is placed into their heaps; then assign a heap number to each heap. Now one heap can be treated as a single datum, i.e. heaps 0x0 to 0x100. Sort the heaps using another technique, like QuickSort.
Now the data is nearly sorted, use multithreading to sort multiple heaps at once. Here I'll use QuickSort again. Since the heaps are sorted, i.e. the largest element in the last heap is no larger than the smallest element in the next, we need not check if the entire array is in order after we sort each heap, for it is by definition always true after we sort each heap separately
In this sample size of 65536, we only need to compare the whole array against a number once, which is faster than the method shown
I like how they all have different tables
*The time complexities are*
Best: O(nlogn)
Average: O(nlogn)
Worst: O(nlogn)
Storage: O(1)
The "click here" parts in the video didn't work for me. The only thing that happened was it paused and restarted the video. Can you put links to the other videos in the description?
Done.
@@udiprod Thanks!
i am never going to use this information, but i'm still watching it
堆積排序法：將排列按亮度排成樹狀圖（堆積化），取得最亮後從底部取一顆球置於頂部。頂部與支部比較，和最亮的交換，逐一比較直至底部。以上步驟反覆進行直至取完全部的球。
堆積排序法因更多次的比較而不如合併排序法快速。合併排序法需要額外的整排空間，而堆積排序法只需要較少的空間。
快速排序法平均而言比合併排序法和堆積排序法都要快，但遇到最槽情況時會更慢，此時堆積排序法會比較快。
當空間不足且不允許忽快忽慢時，堆積排序法較優。
@2:22 why are the leaves sorted??
Why did u stopped making videos. They are so good
Do gravity sort
That would be quite a show
"SORT SESAME" And then they change color
I cant wait to see your next vid keep up the great work
Jonathan Turner Thanks! :)
What's the worst non-randomised sorting algorithm that does no redundant statements?
probably bubble sort
I'd agree with Dustin.
do you count stooge sort as doing no redundant statements?
It would be interesting to "hand trace" a small manageable example like this and count the number of swaps using the traditional method (of just "popping" the top element), vs. my idea of popping the top 2 elements (the root and the brighter of the children in this example). I am thinking if the number of swaps is less using my method, it is a valid improvement and should make runtime on a more substantial tree (such as 1 million random numbers), get sorted faster with "double pop" heapsort. The idea is to get the known 2 brightest balls out of the heap quicker (than 1 at a time).
why at 1:20 black ball didnt spaw with left again ?
It swaps with the brighter of the two, and the right one is a bit brighter. Swapping with the brighter one makes sure the new parent will be brighter than both its children.
Brightest ball is put aside
Tree: _wait, that's illegal_
These type of sorts are mainly for educational purposes only since counting sort seems to be very fast for a reasonable number of possible values and is much simpler to implement. I tried implementing heapsort but I got myself into a heap of trouble.
I don't think this would be a really good idea (since the algorithm is just too difficult to understand), but Tim sort looks like a really popular algorithm nowadays (Python and Open JDK implement it). There's also some stupid algorithms like Slowsort or one I implemented called "Permutation sort", which checks every single permutation of the array until it finds the ordered one. Anyway, I really like how easy to understand are your videos!
Permutation Sort is another name for Bogo Sort.
Is the heap sort faster if you start out with an existing heap and need to sort it?
Implementing Heap Sort is kinda a good way to understand trees
"First, we'll find the brighter of the two children!" 2:12
Can you do Cocktail Shaker sort vs. Merge sort, Quick sort and Heap sort?
Hey, why don't you have a return to bubble sort and have selection sort? And then maybe after that, insertion sort. Then shell sort or comb sort with the faster ones.
selection sort is not needed because he did insertion sort; if she is a girl, selection sort is not needed because she did insertion sort
groszak1
I don't understand your reasoning
learn English
groszak1
Weirdness*
You seriously think English is weird?
why do we use heap sort if merge sort is quicker ?
So if making a heap already organizes the list somewhat, then what’s the point in the heap? Seems rather inefficient compared to other algorithms...
0:39 "now the tree is in an illegal state"
FBI OPEN UP!
Places:
1. Merge Sort (25, 23)
2. Heap Sort (39)
3. Quick Sort (21, 33)
4. Bubble Sort (44)
Will you do radix sort in the future?
I might. It's an interesting algorithm. It would have to look very different than the current way I visualize sorting algorithms, since radix sort relies on digits of numbers, so sorting by colors won't work well.
udiprod
Shell sort or comb sort?
Finally! A new video!
This video distorts the value of Heap Sort:
Heaps/Heap sort is nice when you have big sets (of colored marbles). And when marbles are added (This keeps previous sorted 'info', without the need for new comparisons/recalculations)
Marksman560 You are talking about heaps in general. Heap-sort is a sorting algorithm that uses a heap, but it can't handle new marbles. It has to restart sorting from scratch. Btw, I did mention heap sort has some benefits in the accompanying link zutopedia.com/hs_vs_ms.html
And you are right, perhaps it's worth a mention that heaps by themselves have some great benefits of their own.
When will you make more videos? Your videos are interesting.
Anastasia Dunbar Thanks a lot :) I hope to finish a new video about physics in 2-3 months. I hope you'll find it interesting too.
Wonder what software was used to make this video
Wait a minute. Since Heap sort relies on the fact that the element is sorted from lightest to darkest, couldn't it theoretically faster than merge-sort? As the heapify process is actually sorting from darkest to lightest but in reverse.
I've tested heap sort with a bigger sample, and heap sort seems to do better than or equally as good as merge sort most of the time
Can we get an animation that uses numbers instead of colors?