A derivation of the curve that is approximated by a common visualization of the bubble sort diagram.
Read the full proof on my site: https://linesthatconnect.github.io/blog/a-rigorous-derivation-of-the-bubble-sort-curve/
After uploading, I learned that this result appeared in the paper "Nonparametric testing via partial sorting" by Krzysztof Bisewski, H. M. Jansen, and Yoni Nazarathy. Read it here: https://arxiv.org/abs/2210.14546
The viral sorting algorithm video which first sparked my interest: https://www.youtube.com/watch?v=kPRA0W1kECg
The animations in this video were created using Manim: https://www.manim.community/
Music credits:
Fluidscape by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/by/4.0/
Night Music by Kevin Macleod
river - Calm and Relaxing Piano Music by HarumachiMusic
... And a couple of my own songs:
The Fog: https://soundcloud.com/lines-that-connect/the-fog
Heavy Head, Light Rain: https://soundcloud.com/lines-that-connect/heavy-head-light-rain
Thanks For Watching: https://soundcloud.com/lines-that-connect/thanks-for-watching
Chapters:
00:00 Intro:
0:37 Laying the Background
3:20 How Bubble Sort Works
6:59 Mathematically Describing Diagrams
9:13 Stretching the Diagrams
11:52 Visual Derivation
14:38 Symbolic Derivation
16:48 Nice!
17:07 A Rigorous Solution