Get the latest tech news
A Rigorous Derivation of the Bubble Sort Curve
This post follows my video, The Bubble Sort Curve. You’ll probably want to watch that first.
But I don’t necessarily expect you to enjoy reading through pages of proofs, and all the technical details might obscure the intuition behind the main ideas. Right now, we don’t know if bubble sort forms any shape at all by this definition, since we haven’t proven that every point of the unit square is either included or excluded. The proof for these rules is not particularly glorious; it involves iterating through all the configurations of points at certain cardinal directions, and analyzing the behavior using theorems which didn’t make the cut for this blog post.
Or read this on Hacker News