love the bit about gamma, really great video

Watching this makes me want to replay [the] Gnorp Apologue...

HAAAAAHAAAHAAHAHAHAHAHAHHHAHA

Best video ever thanks for that !

1:40 how to prove Hx＝d/dx ln(x!)+γ

1:40 how to prove Hx＝d/dx ln(x!)+γ

Interesting video, but the music is distracting.

This thing was so dope. You sir are really cool

When handling that a>=b constraint at 16:17, you skipped the implied b!=0 constraint from dividing by b, which results in a t!=0 constraint for the curve overall. That makes sense to me though, because without the t!=0 constraint, it would be implying that unsorted, uniformly-distributed data approaches this curve.

Saw this was 20 minutes and knew it was going to be a banger haven’t seen it yet but I just know

what is that second curve formed by pure white at the bottom of the 59 minute video 0:40

oddly satisfying

11:14 why were these curves animated? It’s confusing me

Very interesting and inspiring video, blog, and draft. However, from the mathematical point of view, there is some discrepancy between what you claimed to prove and what you actually proved. First of all infinities and probabilities are tricky things together, as probability is a measure of its own kind, it needs to be carefully studied so that the events stay in controllable size when approaching infinity. Secondly, as the initial state of the list follows a probability distribution, so does the unsorted section after some iterations. From the probabilistic viewpoint, your curve does not seem to represent anything: If we have numbers from 1 to N to be sorted from their uniform random placements and we know that N-n elements are in their correct places, this is not enough information to conclude scale-invariancy nor continuity over the whole domain. If we think about the expected curve, there will be a discontinuity point at 1-t, because if the element x[(1-t)N] is in the end part of the list at the beginning, it will end up in the correct place, otherwise, the (1-t)N'st element is uniformly any element less than x[(1-t)N], therefore, the expected value is: E(X[(1-t)N]) = 0.5*(x[(1-t)N]-1)*t + x[(1-t)N]*(1-t) = x[(1-t)N] - 0.5*(x[(1-t)N]+1)*t. If I use this to scale the function, it mostly undershoots. As an upper bound, it does not make sense either because distribution P(X[k] <= x[k]) is uniform with a minimum P(X[1] <= x[1]) = t as it will be the first element only if it appears on the unsorted side. From this, I can derive feasible upper and lower bounds by setting either E(X[k] <= x[k])=0 or E(X[k] > x[k]) = 0. The upper bound is always greater than N*x/(x+t) and the lower bound surpasses the curve, so it is not representative of the Bubble-sorting behavior as the height of the bars will be always between these values, see illustration at t=0.4 if Wolfram will not fail me: www.wolframalpha.com/input?i=plot+0.4*1%2B%281-0.4%29*k%2B1%2F2+%281-k%29+%28+k+%2B+1%29*%281-0.4%29%2F1%2C+1.4*k%2F%28k%2B0.4%29%2C+%280.4%2B0.6*k%29%28k%2B1%29%2F2%2C+k%3D0..1 What your proof in the paper and blog presents is that the curve Bubble sort algorithm forms, will approach the function x/(x+t). If someone from a college background reads this, limits are usually taught wrong there. Approaching only means that we go towards something, there is no guarantee to reach the limit calculated with a reasonable amount of steps. It also does not mean that the Bubble sort curve can be approximated by its limit as it does not work as a bound.

I need this guys to write my math textbooks

I guessed that the curve is square root of something, now I feel bad about my guessing capabilities

Yo you're f'ing amazing

The line fitting was essentially the climax of this video after all the edging, while the algebraic dance was the final most intense act

euler daddy

i dont get it but the lines r cool

17:45 Just don't die before the next video, leaving us to wonder what the "different line of reasoning" was, hahaha

It's always Euler

No, just no, this did not need to happen. We apparently are running out of math in the world, for people to spend time doing math on this.

Fantastic

It would be interesting to see what stochastic theory would have to say about doing the process in reverse: ie starting with a sorted list, going from left to right and the looping back, randomly swap a pair of adjacent values if they were in order (so that running the process in reverse, the bubble sort algorithm would choose to swap the pair to reorder them). It defines a random walk in the set of permutations of the sorted list, and it could be fun to see what you could get from analysing it (but sadly I only know the very basics).

Great video

Love these nerds

As a computer science student, this is cool as fire🔥

where is stalin sort in the list?

Kurwa

I haven't looked at your paper, but you can get a rigorous derivation by observing that the position x - t after t sweeps is occupied by the minimum of the original value at position x and the (x - t)-th order statistic of the empirical distribution of the first x elements in the original list. By the law of large numbers, the empirical distribution converges in distribution to uniform as the size of the list increases, and the order statistic is almost surely the quantile function. Then you have f(x - t, t) = (x - t)/x.

How do you evaluate the infinite sum?

How does bubble sort form that curve? Simple: since the process begins from the left, once it catches the biggest element in the unsorted section it steals it from the left and moves it to the right. This causes the left side to accrue a deficit of big elements compared to the right side since by the time the swapping process gets to the right side it has likely already found the biggest element in the entire unsorted section.

My favorite algorithm is merge sort 🥰

You're one of the clearest math youtubers out here!

24:31 i've discovered [second derivative of ln(Hyperfactorial(x)]-1 = harmonicnumber(x) - euler-macheroni constant

I thought it would be a logarithm. But it turned out to be a hyperbola. Awesome video!

Can you do one for the double-bubble sort algorithm? I never published that one because it's about as dumb as bubble sort, it was an optimization I made the day they showed me bubble sort in compsci 1: instead of swapping j for j+1, moving j forward, you move j+1 backward. That is to say: you continue until j+1>j, then start looping while j<j-1, then continue. So let's say you have 1 6 3 4 2 5 7, you end up with 1 [3 6] 4 2 5 7 (3>1, continue); 1 3 [4 6] 2 5 7 (4 > 3, continue); 1 3 4 [2 6] 5 7 (2 < 4, begin reverse); 1 3 [2 4] 6 5 7 (2 < 3, continue); 1 [2 3] 4 6 5 7 (2 > 1, resume); 1 2 3 4 [5 6] 7; 1 2 3 4 5 [6 7]2 sorted. It bubbles both ways and it's twice as fast.

bro tryna be 3blue 1brown so hard tho good vid still

OwO So I had an idea for a sorting technique that is done on at the hardware level. and its time to completion is measured in clock cycles and not comparisons. As far as I know it is the fastest way to sort a list that is not blindly guessing 1,2,3,4,5.... Problem is it currently can only sort a finite number of positive whole numbers. to a finite value. Also I lack the software required to simulate it properly. the proof-of-concept did work though.

I think there is a simple way how to calculate this precisely. If someone finds a mistake, feel free to write it in a reply. The result that I get is same as the one you get, but only if number of elements is really high. If number of elements is quite low, the curve will have a sum of bunch of factorials inside. I'm not sure if it can be easily simplified. Definition of problem: Let's have an array with numbers {1, 2, ..., N} and shuffle it randomly. (choose a random permutation uniformly) Now let's define the curve. curve(K, M) is the M-th value of curve after K iterations of bubble sorty. curve(K, M) := highest number from the M most-left values of the partially solved array. The problem is: What is average value of curve(K, M) for uniformly chosen permutation of original array. Observations: Let's look at the (M + K) most-left values from the original array. After K iterations, the highest K out of them will never be on the M most-left positions. After K iterations, on the fist M most-left positions, there can never be a value, that was not one of the (M + K) most-left position. Result: curve(K, M) = M-th lowest value from the (M + K) most-left values from initial array. Choose (M + K) random numbers from {1, 2, ..., N} without repetition. Then curve(K, M) = the M-th lowest from them. This is close to: curve(K, M) ~= N * M / (K + M), which would give us result x / (x + t) which you got. However the real formula for the curve has a sum of bunch of binomial coeficients. curve(K, M) = SUM_{x=1}^{x=N} [x * ((x - 1) choose (M - 1)) * ((N - x) choose K)] / (N choose (M + K)) If you want to know how I calculated the sum, you can ask chat-GPT how to solve: "Out of numbers {1, 2, ..., N} we choose (M + K) without repetition. On average what is the value of the M-th lowest?" That is the real result. If chat-GPT can't give you answer than give him hint: "Use the number of combinations that x can be the M-th lowest number".

What font do you use

Before watching the video my firdt thought is to find the expected increase between co secutive elements and integrate that function

As a self-teaching highschool student, I really appreciate these presentations of wicked and mysterious maths that both presents ideas and some of the actual working-through-it

Wow this video was very helpful and i learned a lot from it!

Before I finished this video, I sense "e" coming up because of self similarity

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.

You could have just said, it makes that shape, because it's a BUBBLE sort, so it forms a bubble, but go on.

love the factorio music

Did you know that bubble sort is very efficient, when you have scrollable memory? I.e. Further away, more time needed to access elements, like a tape.