A few notes which might be of interest, but which didn't fit in the video: - 3:27 - I'm using a loose pseudocode to represent the algorithm as compactly as possible. The for loops go to N - 2, inclusive. For some reason, that felt more natural to me. - Most of the list sorting animations use a more optimized version of the algorithm than what I step through. Since the largest n items are sorted after n iterations, we can stop the scan early, so each iteration is quicker than the last one. I used the slower version for the math because it is simpler to pretend that every iteration takes an equal amount of time. To transform the result into the more optimized version, just replace t with 1 - √(1 - t). - I "cheated" a bit for some of the animations by using specifically designed shuffles to make the curve really clear (0:02, 0:23, 16:54). The curve starts becoming really clear with random shuffles when the size of the list gets into the thousands (like at 2:30). But when the list length is in the low hundreds, it's usually pretty lopsided (like at 1:18). I think the low hundreds size is the most visually pleasing, so I figured that a slightly fudged shuffle was worth the extra visual clarity. - 1:48 - The timings are actually still not quite right here. The time is based on comparisons only; I forgot to take swaps into account. Insertion sort should be about half as fast as it appears.
This is of course a special case. A lot like a giant single deck of cards, each one is unique. Real data or random data rarely comes close to this pattern. But as you stated, a larger data set will produce better curves. It does make for some rather cool visuals.
Another way of deriving the function would be to use probabilities, measuring the probability P[N=n] where n is the number of numbers to the left of an arbitrary position being lower than the number at that position. You could use n as a parameter to find f(n,t)
You made the assumption, that the input data of Bubble Sort is more probably random, than almost sorted. I believe this to be wrong. IMHO, the only useful application of Bubble Sort (beside for educational purposes and making videos about the Bubble Sort Curve ;) is sorting some data which is constantly changing, the changes tend to be small but are highly scattered. One example that comes to my mind is the list of objects to be drawn in a 3D game. Have the objects sorted from "most fragments" to "least fragments", so nearby objects that obstruct other objects get drawn first and thus reduces the overall amount of work to be done drawing farther away objects only to overdraw them an ms later. How, this list will constantly change by the player moving and turning around (and moving objects), but most of this changes tend to be relatively small from frame to frame. So update the array with some measurement of "number of fragments drawn for this object" then resort the stuff using some Bubble Sort variant (maybe just do a constant but small number of iterations each frame, the result doesn't even need to be completely sorted for next frame), making sure the "biggest" objects are drawn first.
Could you make a video showing how yo set up this equation in Desmos Graphing Calculator? I'm a highschooler with not much education on functions, and I want to play around with it.
@@Luna5829I don‘t know if the visuals are all manim, the equations probably are but I think there’s some other software too and it looks GORGEOUS (more so than 3b1b imho)
the way you gray out the inequality and move it to the side, and the way you color and increase or decrease the size of relevant parts of the graphs and equations is SO HELPFUL and i imagine tricky to get exactly right. i really appreciate it
It's actually not that hard to do using manim, it's a single line for each one. What I find impressive is that he even had the idea to do this, in this form, with these positions and timings, and in the end it's really the combination of all these design choices that make this video so beautiful to watch.
@@givrally oh i meant “tricky to get exactly right” as in there’s a ton of feeling out being done for timings and sizes, and the feedback loop is indirect
I saw your presentation about this at a conference, maybe a month ago. I think maybe you said I was the first person you'd met that had seen your videos. This explanation is much clearer. Thank you.
17:50 "Which this epilogue is too small to contain", i.e. it will be proven in 350 years with methods not yet available to us. Here's to hoping 🤞. Great video btw!
This problem has been stuck in my head for a long time. You don't know how surprised and excited I was when I saw this video explaining the exact problem appears in the recommendation! Thank you so much for making this video.
I think the intuitive element of why this shape forms will come from the fact in bubble sort all the larger values will tend to drift to the right more rapidly than the smaller values move left. As you say smaller values will only ever move left once per iteration, but any larger values prior to the largest unsorted value will make multiple moves until the next largest value is found. From this, because the shape we are perceiving comes from the larger values in any local area, then you'll always get a shape that rapidly climbs to start, and increases more gradually towards it's end.
I love the math videos where its not for academic purposes and is just someone talking about and researching something they love. Just started the video but I know im gonna love it, good job
Fantastic video. You found the solution to a "problem" which is utterly useless and would seem to have no practical applications, purely for the joy of discovery and knowledge. And you explained it in a way that even non-mathematicians (i.e. me) can (mostly) understand. Well done, sir. I salute you 🙂
This is extremely cool! You’re essentially something called a “permuton”. These have become a hot topic over the last several years, but I haven’t seen anyone look at the “bubble sort permuton”.
Thank you!!! I've been working on this for so long without having any idea what the proper words are, so I've been stumbling through the dark. This gives me a direction to explore in!
Gorgeous. I always wondered what that curve was approximating, but imagined a proper derivation would be far more complicated than this. You're a smart guy, LTC. Keep it up
The assumption part should also address why you are ignoring the dips and only fitting a tarp-like shape. Because the shape is only apparent to a human eye constantly searching for a pattern if you are using bars. If you use a scatter plot to represent the same process, the "shape" a human eye are seeing will actually become a string instrument, an American football-shaped part before x, and a straight line pass x.
He does explain/define shapes a bit more rigorously in his blog post. His proof, linked in the blog post, formalizes a definition of shapes at the top of page 9 (definition 8).
I absolutely love mathematics that are complex enough to be interesting yet simple enough to not require a degree to understand if explained in an engaging and informative way. And your excellent use of graphics and animation to demonstrate concepts that would otherwise be difficult to express verbally, that is just /chefskiss.
I have been asking myself this very question every now and then for years, but never took the time to look at it closely. I am so glad you made this video and that I found it. Loved it
@@Gordy-io8sb"The 'curve' is just an artifact of how sorting algorithms work." Evidently. Well, for this particular sorting algorithm, at least. Otherwise we wouldn't be talking about it. "There's nothing special about it." That's your opinion.
@@Gordy-io8sb I don't understand people who watch maths videos when they want to claim that everything they find is meaningless. It's interesting. That's enough of a reason.
after 2 years of computer science studies, i can say this is the best explanation of bubble sort I've ever come across, and it isn't even the main point of the video! Thanks a lot, you really deserve more subs
Have you ever seen those memes that say "pick two: Fast, Cheap, Good" Well, I feel like you identified the equivalent for math proofs. "Pick two: Correct, Intuitive, Rigorous" Well, the choice is really which one to exclude. Excluding 'Correct' is not acceptable in math, or really ever, but the video you have provided combined with the long paper proof you worked out have provided all three to those who want it. It is inspiring how well you have found a clever way to explain this without the headache, and how well you have documented it in its most rigorous form in your blog. Thank you. I hope I can one day do work as good as this.
Explaining the shape is fairly straightforward with basically just: tall stuff moves back faster than short stuff moves forward. Short stuff starting in the middle/back takes a while to move forward, so average height there takes a while to drop, so the curve stays flatter while the front gets steep. However, that doesn't give the actual function at all, and I loved the whole explanation, verbal and visual, for how to reach the function
All these years I've noticed that curve and wondered if there was a way of fitting it, but I lacked the mathematical fluency to step through the process you did. Nice.
Thank's man. You really made my night. I commit, I couldn't follow everything you said, but seeing the function draw it's graph was absolutely worth my time. Happy that you're back.
(1:50) I really want a video where they sort with correct proportional speed to eachother. It would be so nice to see, with as many as possible. Same number of items, same starting positions, same delay between each move, just different algorithms.
this is just absolutely crazy. Every time you upload a video you keep surprising me with your everlasting increase in quality. The animations were incredibly smooth, at every single frame i had all the information i needed, no more, no less, and distributed THE best way possible. An incredible aesthetic, beautiful colors and design supporting an explanation that was precise and great. Please keep uploading videos of such quality, you are one the best math youtubers that have ever existed, no doubts at all.
Every time I watch a video about sorting algorithms, a question crosses my mind. There are so many people who have had the same thought as me, and among them, someone has delved deeply into the mathematics and created a video. UA-cam has accurately recommended exactly what I wanted. This is what makes math interesting.
I took the challenge to find the curve myself, and my central idea was this: For the bar height Y to end up at position X after T iterations, there need to have been exactly T bars before position X that were higher than Y. For ease of notation, let's instead talk about the normalized values x = X/N, y = Y/N and t = T/N, where N is the size of the array. The factors N would cancel out in the end anyway. The likelihood of there being exactly k bars higher than y before position x is given by a binomial distribution: P(k) = (1-y)^k * y^(x-k) * (x choose k). For larger N, this distribution contracts around its expected value until in the limit N -> infinity, all the probability mass is _at_ the expected value and we are certain that the condition is fulfilled at step t = (1-y) * x. This doesn't quite define the right curve yet, because the original condition neglected that the bars are moved one spot to the left when an iteration passes them. After t iterations, values are shifted a distance t to the left. We represent this by replacing x with (x+t) in the formula: t = (1-y) * (x+t) t = x + t - y * (x+t) y * (x+t) = x y = x / (x+t) There we go. If we want to include the already sorted bit, we can write y = max( x / (x+t), x ).
Questions like these are why I decided to pursue a degree in mathematics. To be able to finally answer those little nagging questions that occur when looking at something the average person considers mundane. Amazing video! Time to re-watch the other 3!
Videos of people much smarter than me explaining solutions to problems I barely understand, well enough that by the end I think I can pretend I know what they've just said is my favourite genre of UA-cam video
What I like about this is it's an almost frivolous question but then the answer is kinda down to "the internal symmetrys of the algorithm give rise to these shapes" which is kinda a deep thing
I just wanted to say that this is amazing. You provided not only an excellent video for UA-cam, but an entire paper with a mathematical proof for anyone interested in the topic. This is what educational UA-cam videos should be. Great work and please keep going, this is how popularizing math and computer science should look like! Also, the whole premise of this topic is so simple, yet so non-trivial to think about. I'm almost angry that I didn't think about this problem myself :)
This is absolutely beautiful. For many math videos out there, I could guess where it’s heading just from the thumbnail/title. This one stunned me. I guessed that this might need some differential equations or some sort of series and end up with something like natural log. Turns out just a few weeks of Calculus 1 would do. Gorgeous! Edit: I usually don’t give a like to videos, but you deserved it.
This is really good content. It reminds me of my favourite maths youtubers, complete with calm voiceover and helpful and captivating graphics. This really is 10/10 content. Keep up the good work!
I read some pages of the full proof in your description, and I think it is genius! using 3d pespective and shearing the Diagram is an unexpeted but elegant way to proof it. very satisfying work!
I literally just checked your channel last week for any new videos and thought "what a shame, looks like there's no more coming", and then you drop a new vid, let's go!
To say this content is as wonderfully illustrated and animated as the content of this one blue, three brown guy (or whatever his nickname is) wouldn't be an exaggeration. The presentation is nothing short of excellently executed and gives a masterclass in teaching. What a joy to join in and getting educated! Thanks a lot for all the enormous effort and time you put into this marvellous piece of edutainment! 😊
My favourite part about this video is not the bubble sort curve solution, but how harmoniously it illustrates that the *real* intellectual leap is figuring out how to formulate a problem into something one can hold on to and tackle in bits.
this video has some ancient math vibe, when no complicated methods are used, but we still can come up with an elegant solution. i really enjoy that stuff
This was gorgeous! Initially, I didn't know how you would have tackled the problem. As soon you brought out the similarity condition I had an enlightenment. Beautiful problem, beautiful solution, splendid explanation!
Maths grad here - I always assumed the graph was a square root but very happy to be shown wrong! Really liked your assumptions and method its very clever!! Loved the graph stretching and bam they match part that was crazy cool
this is such an interesting application of functional equations, I love how we start with the conditions the functions must satisfy and somehow narrowing it down to one possible solution
I think it's super interesting that, if I understand correctly, you never encoded a directive into your proof that the curve should follow the *peaks*, or like, a convex hull or something, of the bubble sort. You were just like, "let there be a continuous curve that behaves nicely and connects up to the diagonal bit"... and the maths decided to give you back a curve that very specifically follows the peaks/convex hull of the bubble sort... am I missing something, or is that kinda weird?
it's shape reminds me of enzyme kinetics - the graph of reaction rate vs substrate (the reactant) concentration, sort of logarithmic looking but asymptotically approaches a maximum.
Incredible video! I first imagined that some stochastic techniques would be needed, but your parametric approach was simple, comprehensive, and beautiful at once. To generalize the result to non-uniform elements in the array, you can just say that you work with their quantiles.
Wow! This video is less than a day old and has less than 50k views? It seems like the kind of video I'd watch from some giant maths channel that came out several years ago and has amassed millions of views. This has instantly earned my sub
This keeps being recommended to me despite having already watched it multiple times, and yet I keep clicking it because it’s just that good a video (and I might be slightly bored these days with a bit too much time on my hands)
Subscribed. When the music kicks in at 16:54, I got emotional. You do a good job of hinting that this function is recursively defined in nature, which leads to an explicit formula, similar to how some sequences can be solved.
THANK YOU! I have been thinking about this since one of the first times I watched a sorting algorithms video and, as you said, there isn't much information on the internet about this specific problem. This was so cool to watch, you're also a great storyteller.
this s the most satisfying thing i watched in recent days..... we need more videos from you.... amazing stuff.... i have become big fan of your work....
I'm happy that I ended up watching one of your other videos, and then subscribed. I had previously seen this video recommended to me over and over, but thought it was one of those viral sorting algorithm videos and didn't watch it. I'm happy that I was wrong, this video is very interesting and well done!
I figured it out intuitively at about 7 minutes into the video; I realised by sorting from right to left, it is equivelant to simply removing the bars from tallest to shortest while also shifting the shorter ones leftward. That would make a triangle - HOWEVER because you put those tallest bars at the end and 'scrunch up' the gaps they leave, it sort of squishes the triangle leftwards, creating the curve. This is because the larger bars are pushed rightwards every iteration it skews the triangle into the curve.
Wow, this video is fantastic! and the animations are truly impressive!! I'm a Manim animation enthusiast myself, and I'm very interested to see how you achieved these effects. No worries at all if you'd prefer to keep it private, but I truly appreciate your work! Keep up the amazing content!
Nice. When I was watching these visualizations long time ago, I also noticed that it is creating some hyperbola or something, but never digged dipper. Interesting way of using scaling law to figure out the formula. It is still a bit mysterious why it actually works, but I guess, random something something makes it so. Will read your blog too, because it still bugs me up. Really good video.
This is one of those questions that’s been in the back of my mind forever but I haven’t had the patience or motivation to actually figure out the answer to
Wow, this video is spectacular. It reminds me of the story of great animation you get on 3 Blue 1 Brown. Now, you just need to get the same amount of subscribers. Great job.
Bubble sort curve immediately makes sense It goes through the next if its short, and moves the next if its taller Bubble sort always starts at the beginning, so naturally it will form a curve of progressively taller one
My favourite sort algorithm has two major steps: 1- Convert the list into a heap 2- Sort that with "insertion Shell" (as bubble Shell is also possible) In My experiments, at least, it was faster than quick sort. I believe the trick is that in direct quick sort or Shell, can happend that it compares two distant elements, whose in the final list will be next to each other. So, it is almost irrelevant to do the exchange at that moment. But a heap is an "approximate sorted list', so that scenary can't happend. All exchanges becomes much more relevant for obtaining the final sorted list.
A few notes which might be of interest, but which didn't fit in the video:
- 3:27 - I'm using a loose pseudocode to represent the algorithm as compactly as possible. The for loops go to N - 2, inclusive. For some reason, that felt more natural to me.
- Most of the list sorting animations use a more optimized version of the algorithm than what I step through. Since the largest n items are sorted after n iterations, we can stop the scan early, so each iteration is quicker than the last one. I used the slower version for the math because it is simpler to pretend that every iteration takes an equal amount of time. To transform the result into the more optimized version, just replace t with 1 - √(1 - t).
- I "cheated" a bit for some of the animations by using specifically designed shuffles to make the curve really clear (0:02, 0:23, 16:54). The curve starts becoming really clear with random shuffles when the size of the list gets into the thousands (like at 2:30). But when the list length is in the low hundreds, it's usually pretty lopsided (like at 1:18). I think the low hundreds size is the most visually pleasing, so I figured that a slightly fudged shuffle was worth the extra visual clarity.
- 1:48 - The timings are actually still not quite right here. The time is based on comparisons only; I forgot to take swaps into account. Insertion sort should be about half as fast as it appears.
This is of course a special case. A lot like a giant single deck of cards, each one is unique. Real data or random data rarely comes close to this pattern. But as you stated, a larger data set will produce better curves. It does make for some rather cool visuals.
Another way of deriving the function would be to use probabilities, measuring the probability P[N=n] where n is the number of numbers to the left of an arbitrary position being lower than the number at that position. You could use n as a parameter to find f(n,t)
Bro you gotta make more Videos
I enjoy them so much, you have an uncommon Talent in explaining (an manim, i dont get the library -_-)
You made the assumption, that the input data of Bubble Sort is more probably random, than almost sorted. I believe this to be wrong. IMHO, the only useful application of Bubble Sort (beside for educational purposes and making videos about the Bubble Sort Curve ;) is sorting some data which is constantly changing, the changes tend to be small but are highly scattered. One example that comes to my mind is the list of objects to be drawn in a 3D game. Have the objects sorted from "most fragments" to "least fragments", so nearby objects that obstruct other objects get drawn first and thus reduces the overall amount of work to be done drawing farther away objects only to overdraw them an ms later. How, this list will constantly change by the player moving and turning around (and moving objects), but most of this changes tend to be relatively small from frame to frame. So update the array with some measurement of "number of fragments drawn for this object" then resort the stuff using some Bubble Sort variant (maybe just do a constant but small number of iterations each frame, the result doesn't even need to be completely sorted for next frame), making sure the "biggest" objects are drawn first.
Could you make a video showing how yo set up this equation in Desmos Graphing Calculator? I'm a highschooler with not much education on functions, and I want to play around with it.
The most impressive part of it is that you did not skip the rigor, you wrote up a 26 page paper exploring the details. Really cool video.
HE WROTE A PAPER ALONGSIDE THIS VIDEO?
Holy sh-
Edit: just finished the video and oh my God the madman actually did
average lsgp strat
@@Prograde what the fuck why are you here
mcpk meetup moment
@@kurrycat what the fuck you too 😭😭
5.15.24
the curve matching is a lot more satisfying than any sorting video i have seen
The entire derivation build up made it so satisfying to see it smoothly lock into place after all his work
k
u
v
I
n
a
manim has such good-looking visuals istg
it's made by 3b1b so that's why you might see some similarities in the visuals
I watched that and could not stop myself from saying "nice", just to here "nice" in my ears a few seconds later 😂
@@Luna5829I don‘t know if the visuals are all manim, the equations probably are but I think there’s some other software too and it looks GORGEOUS (more so than 3b1b imho)
You realize you probably have one of the best average video quality on UA-cam, right? 4 videos, all killer, no filler.
he is the next 3b1b i think
Lol @ best average video quality
I know quite a few channels with very few very high-quality videos, such as Nemean and CodeAesthetic, and they happen to both be programming-related.
Joshs Channel also up there
a channel with a single, great, video is better :)
the way you gray out the inequality and move it to the side, and the way you color and increase or decrease the size of relevant parts of the graphs and equations is SO HELPFUL and i imagine tricky to get exactly right. i really appreciate it
It's actually not that hard to do using manim, it's a single line for each one. What I find impressive is that he even had the idea to do this, in this form, with these positions and timings, and in the end it's really the combination of all these design choices that make this video so beautiful to watch.
@@givrally oh i meant “tricky to get exactly right” as in there’s a ton of feeling out being done for timings and sizes, and the feedback loop is indirect
I saw your presentation about this at a conference, maybe a month ago.
I think maybe you said I was the first person you'd met that had seen your videos.
This explanation is much clearer. Thank you.
Hey David, it was nice to meet you at the conference! I'm glad this approach worked for you
16:22 I can't even imagine the work you put in that ≥ to ≤ transition in manim. Great video as always.
I'm so glad this didn't go unnoticed! It's the kind of thing where you'd never think it takes so much work unless you've tried it yourself.
@@LinesThatConnect I haven't tried it and I was still in awe. I saw the equations dissolve and I was like "Wow, that was impressive."
how's that impressive, I don't get it
@@higztv1166 Editing anything takes so much obnoxiously longer than you'd expect.
@@higztv1166 try to animate it yourself and you'll see
Bro just comes in every year or so and just drops a banger on us
I just checked: It has been 08/2021, 08/2022, 04/2023, and this month 04/2024.
See you in 2025.
Bro took quality over quantity to heart
17:50 "Which this epilogue is too small to contain", i.e. it will be proven in 350 years with methods not yet available to us. Here's to hoping 🤞. Great video btw!
Fermat moment
i thought of this exact same thing xD
Lets wait for 2374 :D
@@Rudxain FERMAT C: … uh oh I erased the data
lmao yep
Babe not now, factorial guy just dropped
I, Newton, have also come to witness this event.
yes yes yes
😂
@@Sir_Isaac_Newton_SIR ISSAC NEWTON 🗣️🗣️🗣️
Lmaoooo
0:33 it's called Churgleture and it is a measure of how bigly the datum is
This problem has been stuck in my head for a long time. You don't know how surprised and excited I was when I saw this video explaining the exact problem appears in the recommendation! Thank you so much for making this video.
Same.
Same
Sam
Why??? Why would you want to know a formula for the shape of the bubble sort curve?
@@JavedAlam-ce4muIt isn't that strange to see someone have curiosity for a random topic.
I think the intuitive element of why this shape forms will come from the fact in bubble sort all the larger values will tend to drift to the right more rapidly than the smaller values move left. As you say smaller values will only ever move left once per iteration, but any larger values prior to the largest unsorted value will make multiple moves until the next largest value is found.
From this, because the shape we are perceiving comes from the larger values in any local area, then you'll always get a shape that rapidly climbs to start, and increases more gradually towards it's end.
I love the math videos where its not for academic purposes and is just someone talking about and researching something they love. Just started the video but I know im gonna love it, good job
Fantastic video. You found the solution to a "problem" which is utterly useless and would seem to have no practical applications, purely for the joy of discovery and knowledge. And you explained it in a way that even non-mathematicians (i.e. me) can (mostly) understand. Well done, sir. I salute you 🙂
You went this far.. for a sorting algorithim?
Absolutely insane. It was satisfying as hell watching the curve plotted against sorting.
he went this far for a sorting algorithm that nobody uses... but that fits exactly what I imagine mathematicians doing with their day.
The pursuit of truth is what makes the journey
That final animation of the curve that you found matching the data so smoothly was...jaw-dropping. 😲
This is extremely cool! You’re essentially something called a “permuton”. These have become a hot topic over the last several years, but I haven’t seen anyone look at the “bubble sort permuton”.
Thank you!!!
I've been working on this for so long without having any idea what the proper words are, so I've been stumbling through the dark. This gives me a direction to explore in!
Gorgeous. I always wondered what that curve was approximating, but imagined a proper derivation would be far more complicated than this. You're a smart guy, LTC. Keep it up
The assumption part should also address why you are ignoring the dips and only fitting a tarp-like shape. Because the shape is only apparent to a human eye constantly searching for a pattern if you are using bars.
If you use a scatter plot to represent the same process, the "shape" a human eye are seeing will actually become a string instrument, an American football-shaped part before x, and a straight line pass x.
He does explain/define shapes a bit more rigorously in his blog post. His proof, linked in the blog post, formalizes a definition of shapes at the top of page 9 (definition 8).
I absolutely love mathematics that are complex enough to be interesting yet simple enough to not require a degree to understand if explained in an engaging and informative way. And your excellent use of graphics and animation to demonstrate concepts that would otherwise be difficult to express verbally, that is just /chefskiss.
I have been asking myself this very question every now and then for years, but never took the time to look at it closely. I am so glad you made this video and that I found it. Loved it
The "curve" is just an artifact of how sorting algorithms work. There's nothing special about it.
@@Gordy-io8sb"The 'curve' is just an artifact of how sorting algorithms work."
Evidently. Well, for this particular sorting algorithm, at least. Otherwise we wouldn't be talking about it.
"There's nothing special about it."
That's your opinion.
@@Gordy-io8sbEuler's constant is just an artifact of how exponential growth works. There's nothing special about it.
@@Gordy-io8sb I don't understand people who watch maths videos when they want to claim that everything they find is meaningless. It's interesting. That's enough of a reason.
@@thesecondderivative8967 Are you implying I'm one of those people? Let me tell you, those people are pseudo-intellectuals. I am above them.
after 2 years of computer science studies, i can say this is the best explanation of bubble sort I've ever come across, and it isn't even the main point of the video! Thanks a lot, you really deserve more subs
Perfect video to watch right before bed answering a question I’ve thought about and never bothered to answer myself
16:48 for anyone wanting to graph this in desmos, to turn it into a recreation of the optimised bubble sort:
- add the equations "y = {0
If you have a link to a public Demos graph of this that would be great!
t_{n}
First line: y=\left\{0\le x\le1-t:\frac{x}{x+t}
ight\}
Second line: y=\left\{1-t
Have you ever seen those memes that say "pick two: Fast, Cheap, Good"
Well, I feel like you identified the equivalent for math proofs. "Pick two: Correct, Intuitive, Rigorous"
Well, the choice is really which one to exclude. Excluding 'Correct' is not acceptable in math, or really ever, but the video you have provided combined with the long paper proof you worked out have provided all three to those who want it. It is inspiring how well you have found a clever way to explain this without the headache, and how well you have documented it in its most rigorous form in your blog. Thank you. I hope I can one day do work as good as this.
You should do a whole video on the Euler-Mascheroni constant, would be really interesting in your style
Who would eat oiler maccaroni?
@@chaotickreg7024 oiled up mammamia
great video, and really smooth graphics! always interesting to see maths applied to subjects where it isn't necessary
YOOO lines that connect is back !!
Explaining the shape is fairly straightforward with basically just: tall stuff moves back faster than short stuff moves forward. Short stuff starting in the middle/back takes a while to move forward, so average height there takes a while to drop, so the curve stays flatter while the front gets steep. However, that doesn't give the actual function at all, and I loved the whole explanation, verbal and visual, for how to reach the function
All these years I've noticed that curve and wondered if there was a way of fitting it, but I lacked the mathematical fluency to step through the process you did. Nice.
Thank's man. You really made my night. I commit, I couldn't follow everything you said, but seeing the function draw it's graph was absolutely worth my time. Happy that you're back.
(1:50) I really want a video where they sort with correct proportional speed to eachother. It would be so nice to see, with as many as possible. Same number of items, same starting positions, same delay between each move, just different algorithms.
this is just absolutely crazy. Every time you upload a video you keep surprising me with your everlasting increase in quality.
The animations were incredibly smooth, at every single frame i had all the information i needed, no more, no less, and distributed THE best way possible.
An incredible aesthetic, beautiful colors and design supporting an explanation that was precise and great.
Please keep uploading videos of such quality, you are one the best math youtubers that have ever existed, no doubts at all.
Just amazing. Love the “nice” moment. Please keep posting!!! Love your stuff!!!
Every time I watch a video about sorting algorithms, a question crosses my mind. There are so many people who have had the same thought as me, and among them, someone has delved deeply into the mathematics and created a video. UA-cam has accurately recommended exactly what I wanted. This is what makes math interesting.
Your videos are some of few where you can watch them an unlimited amount of time and still learn something new every time. Keep up the great work.
Been a while! Glad to see you’re back.
Whoa. I’m not a maths person but what little I got was beautiful. I feel like I understand why people enjoy maths a bit better.
I took the challenge to find the curve myself, and my central idea was this:
For the bar height Y to end up at position X after T iterations, there need to have been exactly T bars before position X that were higher than Y.
For ease of notation, let's instead talk about the normalized values x = X/N, y = Y/N and t = T/N, where N is the size of the array. The factors N would cancel out in the end anyway.
The likelihood of there being exactly k bars higher than y before position x is given by a binomial distribution:
P(k) = (1-y)^k * y^(x-k) * (x choose k). For larger N, this distribution contracts around its expected value until in the limit N -> infinity, all the probability mass is _at_ the expected value and we are certain that the condition is fulfilled at step t = (1-y) * x.
This doesn't quite define the right curve yet, because the original condition neglected that the bars are moved one spot to the left when an iteration passes them. After t iterations, values are shifted a distance t to the left. We represent this by replacing x with (x+t) in the formula:
t = (1-y) * (x+t)
t = x + t - y * (x+t)
y * (x+t) = x
y = x / (x+t)
There we go. If we want to include the already sorted bit, we can write y = max( x / (x+t), x ).
Bravo, I'm jealous of how quickly you came up with that! That's the gist of my rigorous approach, but it took me a crazy long time to think of it.
This style is fantastic. I’m a community college dropout and I understood this entire video while stoned out of my body. Absolutely impressive work!!
Questions like these are why I decided to pursue a degree in mathematics. To be able to finally answer those little nagging questions that occur when looking at something the average person considers mundane. Amazing video! Time to re-watch the other 3!
Videos of people much smarter than me explaining solutions to problems I barely understand, well enough that by the end I think I can pretend I know what they've just said is my favourite genre of UA-cam video
What I like about this is it's an almost frivolous question but then the answer is kinda down to "the internal symmetrys of the algorithm give rise to these shapes" which is kinda a deep thing
I love when u come up with those problems they are very unique and special also how u make it easier to understand by this animation. Keep going bro
I think I could watch hours of bubble sorts with the curve overlaid. That was so good.
I just wanted to say that this is amazing. You provided not only an excellent video for UA-cam, but an entire paper with a mathematical proof for anyone interested in the topic. This is what educational UA-cam videos should be. Great work and please keep going, this is how popularizing math and computer science should look like! Also, the whole premise of this topic is so simple, yet so non-trivial to think about. I'm almost angry that I didn't think about this problem myself :)
This is absolutely beautiful. For many math videos out there, I could guess where it’s heading just from the thumbnail/title. This one stunned me. I guessed that this might need some differential equations or some sort of series and end up with something like natural log. Turns out just a few weeks of Calculus 1 would do. Gorgeous!
Edit: I usually don’t give a like to videos, but you deserved it.
I knew you first with this video, thought you were a coding guy. You were an awesome math guy. Very impressed!
This is really good content. It reminds me of my favourite maths youtubers, complete with calm voiceover and helpful and captivating graphics. This really is 10/10 content. Keep up the good work!
One little addition to the graph: you picked the scale 1x1 so everything outside 0
This was honestly beautiful, an incredible example of the mathematical analysis that happens in computer science
I read some pages of the full proof in your description,
and I think it is genius!
using 3d pespective and shearing the Diagram is an unexpeted but elegant way to proof it.
very satisfying work!
I literally just checked your channel last week for any new videos and thought "what a shame, looks like there's no more coming", and then you drop a new vid, let's go!
To say this content is as wonderfully illustrated and animated as the content of this one blue, three brown guy (or whatever his nickname is) wouldn't be an exaggeration. The presentation is nothing short of excellently executed and gives a masterclass in teaching. What a joy to join in and getting educated! Thanks a lot for all the enormous effort and time you put into this marvellous piece of edutainment! 😊
My favourite part about this video is not the bubble sort curve solution, but how harmoniously it illustrates that the *real* intellectual leap is figuring out how to formulate a problem into something one can hold on to and tackle in bits.
this video has some ancient math vibe, when no complicated methods are used, but we still can come up with an elegant solution. i really enjoy that stuff
I used to suggest 3b1b for math videos to all my math students, but now I suggest LTC, it's just pure magic to be honest.
Why not both?
This was gorgeous! Initially, I didn't know how you would have tackled the problem. As soon you brought out the similarity condition I had an enlightenment. Beautiful problem, beautiful solution, splendid explanation!
Maths grad here - I always assumed the graph was a square root but very happy to be shown wrong! Really liked your assumptions and method its very clever!! Loved the graph stretching and bam they match part that was crazy cool
Really interesting concept to explore, the a-ha moment at 14:23 really did it for me. Awesome stuff!
this is such an interesting application of functional equations, I love how we start with the conditions the functions must satisfy and somehow narrowing it down to one possible solution
I think it's super interesting that, if I understand correctly, you never encoded a directive into your proof that the curve should follow the *peaks*, or like, a convex hull or something, of the bubble sort. You were just like, "let there be a continuous curve that behaves nicely and connects up to the diagonal bit"... and the maths decided to give you back a curve that very specifically follows the peaks/convex hull of the bubble sort... am I missing something, or is that kinda weird?
math do be like that
Perhaps that property is implicitly included via the “identical starting sections look the same regardless of proceeding data” property?
it's shape reminds me of enzyme kinetics - the graph of reaction rate vs substrate (the reactant) concentration, sort of logarithmic looking but asymptotically approaches a maximum.
Never thought about this before, but the moment I saw the thumbnail I was intrigued!
Incredible video! I first imagined that some stochastic techniques would be needed, but your parametric approach was simple, comprehensive, and beautiful at once.
To generalize the result to non-uniform elements in the array, you can just say that you work with their quantiles.
Wow! This video is less than a day old and has less than 50k views? It seems like the kind of video I'd watch from some giant maths channel that came out several years ago and has amassed millions of views. This has instantly earned my sub
This keeps being recommended to me despite having already watched it multiple times, and yet I keep clicking it because it’s just that good a video (and I might be slightly bored these days with a bit too much time on my hands)
Subscribed. When the music kicks in at 16:54, I got emotional. You do a good job of hinting that this function is recursively defined in nature, which leads to an explicit formula, similar to how some sequences can be solved.
This is the kind of content I love most, even if I don't end up watching them most. Excellent job!
Wonderful! Informative! Well presented, written, and recorded! Please continue doing this, keep up the excellent work
One of the most beautiful videos I’ve watched in a while, this is why I love maths.
Amazing display of creativity. Congrats and thank you!
Nice video. The derivation of the closed form was well established and you answered all key question I'd worry about.
Great topic choice, well-explained solution, and beautifully animated!
THANK YOU! I have been thinking about this since one of the first times I watched a sorting algorithms video and, as you said, there isn't much information on the internet about this specific problem. This was so cool to watch, you're also a great storyteller.
I missed your videos, glad to see you again my guy
this s the most satisfying thing i watched in recent days..... we need more videos from you.... amazing stuff.... i have become big fan of your work....
Amazing! Always like to find the limits of discrete processes. Thank you
I’ve been wondering about this exact question for years. Thank you so much!
You're one of the clearest math youtubers out here!
What a great question to ask! I could've watched a dozen more examples of the curve perfectly matching a real sorting like 16:54
I'm happy that I ended up watching one of your other videos, and then subscribed. I had previously seen this video recommended to me over and over, but thought it was one of those viral sorting algorithm videos and didn't watch it. I'm happy that I was wrong, this video is very interesting and well done!
I figured it out intuitively at about 7 minutes into the video; I realised by sorting from right to left, it is equivelant to simply removing the bars from tallest to shortest while also shifting the shorter ones leftward. That would make a triangle - HOWEVER because you put those tallest bars at the end and 'scrunch up' the gaps they leave, it sort of squishes the triangle leftwards, creating the curve. This is because the larger bars are pushed rightwards every iteration it skews the triangle into the curve.
Wow, this video is fantastic! and the animations are truly impressive!! I'm a Manim animation enthusiast myself, and I'm very interested to see how you achieved these effects. No worries at all if you'd prefer to keep it private, but I truly appreciate your work! Keep up the amazing content!
Nice. When I was watching these visualizations long time ago, I also noticed that it is creating some hyperbola or something, but never digged dipper.
Interesting way of using scaling law to figure out the formula. It is still a bit mysterious why it actually works, but I guess, random something something makes it so. Will read your blog too, because it still bugs me up.
Really good video.
After all the work to see the curve fit so well... perfection
Finally. A video that answered a long-standing question of mine. I can now rest in peace. 😌
This is one of those questions that’s been in the back of my mind forever but I haven’t had the patience or motivation to actually figure out the answer to
I love this channel, like 3b1b, but the topics are much easier to understand
ive been thinking of investigating this myself! im so happy to see this video
Thank you! The first time I've watched some animated sorting algo comparision I asked myself the same question.
Wow, this videos has such high production quality!
Wow, this video is spectacular. It reminds me of the story of great animation you get on 3 Blue 1 Brown. Now, you just need to get the same amount of subscribers.
Great job.
Bubble sort curve immediately makes sense
It goes through the next if its short, and moves the next if its taller
Bubble sort always starts at the beginning, so naturally it will form a curve of progressively taller one
Idk why youd want to know the math behind it. If you understand it and can make it, then thats all that matters
I can't believe this problem would be solved so elegantly!
This was genuinely beautiful
what an amazing derivation, so simple yet so satisfying
Finally, I thought for a second that no more videos would accur and yet, boom, here you are! Great to see you back!
My favourite sort algorithm has two major steps:
1- Convert the list into a heap
2- Sort that with "insertion Shell" (as bubble Shell is also possible)
In My experiments, at least, it was faster than quick sort. I believe the trick is that in direct quick sort or Shell, can happend that it compares two distant elements, whose in the final list will be next to each other. So, it is almost irrelevant to do the exchange at that moment. But a heap is an "approximate sorted list', so that scenary can't happend. All exchanges becomes much more relevant for obtaining the final sorted list.
Really cool video, I have watched at 3:45am and I understood it perfectly.