The Density of Bubble Sort Plots

In my previous post, I shared a precise definition of what it means for a sorting algorithm’s scatter plot to approach a shape. I then showed that, as per this definition, bubble sort really does approach the curve derived in my video. Loosely speaking, the shape of a sorting algorithm was defined to be the set of points that is almost always “filled up” by the points in the algorithm’s scatter plots. But this definition ignores an interesting detail: how densely are different parts of the shape filled?

In this post, we’ll answer that question for bubble sort. We’ll be referring to the topics discussed in the other post, so you might want to read it if it feels like I pull something out of thin air.

What am I talking about?

Here’s a scatter plot of bubble sort, with the points categorized into three colors.

Clearly, the sorted section (green) is the most dense; the points are so tightly packed that it looks like a solid line. On the other hand, the interior of the unsorted section (blue) is the least dense. But the interesting part is the curve (red). The red points are way more densely packed than the blue points, but by how much exactly? How can we measure this?

Well to be honest, I don’t know the standard mathematical formulation of this question. I only know the most basic rudiments of probability theory, and the tools to tackle this problem are beyond any class I’ve taken. But if you’ll bear with me as I reinvent the wheel, I think you’ll agree that my answer is reasonable enough.

Unlike in my previous post, I think it is natural to consider the diagrams to be 2D when talking about the point density. We’ll consider the diagrams to have a width and height of 1; they will be contained in the unit square $[0, 1]^2$. We will also let $t \in [0, 1]$ represent the progress of the algorithm.

Defining Density

The idea is not too complex. Draw a little disc over the diagram. Find the proportion of the diagram’s points which are inside the disc. Divide this by the disc’s area to get its density. Then, by finding the densities of smaller and smaller discs, we can zero in on the density at a specific point.

To be more specific, we can let $r$ be the radius of the disc, let $N$ be the number of point in the diagram, and let $k$ be the number of diagram points which are inside the disc. The density is then

$$\frac k{\pi r^2 N}.$$

In reality, $k$ would be a random variable and we would need to take some kind of probabilistic limit as $N \to \infty$. But I don’t want to get too complicated, so let’s not worry about the technicalities.

This definition actually has a big problem: Some parts of bubble sort’s diagrams will be infinitely dense! This is because we’re assuming that the points are spread out over a 2D region, like they are in the blue section of the diagram above. But the red and green points are tightly compressed into a 1D curve. Dividing by the disc’s area only works when $k/N$ is proportional to its area.

But in these one-dimensional sections, we’ll find that $k/N$ is proportional to the disc’s diameter. So the fix is simple: for the red and green points, use the disc’s diameter instead of its area. Then the density will be

$$\frac k{2rN}.$$

For each part of the diagram, we’ll use the appropriate definition of density, keeping in mind that every diameter-based density is “infinitely greater” than every area-based density.

The Easy Parts: Green and Blue

Let’s start with the sorted section (the green points). Since this is clearly a one-dimensional line, we will use the one-dimensional version of density. So, picking some point on the line, draw a disc of radius $r$. For a list of $N$ items, the horizontal distance between the points is $1/N$. Since the points are all lined up at a $45\degree$ angle, they only intersect the disc over a width of $r\cdot\sin(45\degree) = r\sqrt2$.

Therefore $k$, the number of items in the disc, will be about $Nr\sqrt2$. So the density is

$$\frac k{2rN} = \frac{rN\sqrt2}{2rN} = \frac{\sqrt2}2.$$

Since this doesn’t depend on $r$, it will remain unchanged as $r \to 0$, so $\sqrt2/2$ is our final answer for the density of the sorted section.

The blue points are also pretty easy. These are the points which are lower than some point before them. I won’t go into detail here, but if you’re familiar with bubble sort, you can reason that these points move precisely one space to the left each iteration as a higher point passes over them. But since these blue points all move one space to the left — no more, no less — they don’t move relative to each other. This means that the density of the blue section will not change from what it was in the initial state of the list!

An important fact from my previous post is that, in the initial state of the list, the points are spread uniformly over the unit square. That is, if you draw some shape in the unit square, then the proportion of the diagrams points which are inside the shape will converge to the shape’s area as you consider larger and larger lists. So, letting the shape be our circle of radius $r$, we find that the density is

$$\frac kN \cdot \frac1{\pi r^2} = \pi r^2 \cdot \frac1{\pi r^2} = 1.$$

(Remember that for the blue part we used the two-dimensional density, but for the green part we used the one-dimensional density. Even though the number we got for the blue part, $1$, is greater than the number we got for the green part, $\sqrt2/2$, the green part is still infinitely more dense than the blue part.)

The Fun Part: The Red Curve

Here’s where we really start needing some ideas from my previous post. We’re going to shift the diagram to the right by the amount of time that has passed. That is, we’ll move every point $(x, y)$ to $(x + t, y)$. This makes it so that no points ever move left as the algorithm runs. But more importantly, it allows us to draw boxes over the diagram, and the numbers of items in the boxes will change according to some simple rules. These rules are listed in here, but for our purposes we’ll only need one consequence of them:

No points can leave a box unless there are no points above it.

In other words, if we have two boxes $B$ and $C$ like this, no points will be able to leave $B$ until $C$ is completely empty.

With this in mind, let’s draw some boxes over the curve:

I chose these boxes specifically so that two corners of box $B$ lie on the curve. Let’s think about this situation for a minute. Since the curved region shrinks toward the bottom right corner as $t$ increases, it was passing through $C$ until this exact moment. This means that, up until now, $C$ was not empty, so no points could have left $B$.

Also, $A$ is empty at this point in time. Since the points only move laterally, all of the points from $A$ must have moved into $B$. But they can’t have left $B$ because $C$’s former non-emptiness disallowed it. So all the points which started in either $A$ or $B$ have been crammed into $B$.

Now because of the initial uniformity of the points, the proportions of the points which started in $A$ and $B$ approach the respective areas of $A$ and $B$. Since all these points have moved into $B$, we have that

$$\frac{\text{Number of points in $B$}}N = \text{Area}(A) + \text{Area(B)}.$$

With this fact under our belt, we can make $B$ smaller and smaller, which allows us to zero in on the point density of the curve.

Getting Differential

We’ll pick some point $(x, y)$ on the curve, and draw a disc with tiny radius $r$ centered there. We can then construct the boxes $A$, $B$, and $C$ as above, with $B$ inscribed in the disc.

Now, let’s give names to some of the dimensions in this diagram. We’ll call $B$’s width $dx$, we’ll call its height $dy$, and we’ll its diagonal $ds$.

Since the red diagonal line is just a really zoomed-in picture of the curve, these values are the curve’s differentials. This red segment is also a diameter of the disc, so

$$2r = ds = \sqrt{dx^2 + dy^2}.$$

Now, we can start thinking about the density. Let’s again let $k$ represent the number of points in the disc. We can see that

$$\frac kN = \frac{\text{Number of points in $B$}}N + O(r^2).$$

The $O(r^2)$ comes from the points that are in the disc, but not in $B$. These points are all blue, so we already saw that their contribution is proportional to $r^2$, evident by the fact that the area-based density definition gave a finite value. These points will turn out to be negligible when we use the diameter-based definition of density, so we can just use big O notation and not worry about the specifics.

Applying the result of the previous section, we have

$$\frac kN = \text{Area}(A) + \text{Area}(B) + O(r^2).$$

But what are these areas? Well, both boxes have a height of $dy$, the width of $A$ is $x - dx/2$, and the width of $B$ is $dx$. So, keeping in mind that both $dx$ and $dy$ are $O(r)$, we have

$$\begin{aligned} \text{Area}(A) + \text{Area}(B) &= \left(x - \frac{dx}2\right)dy + dx dy\\ &= xdy + \frac12 dx dy\\ &= xdy + O(r^2). \end{aligned}$$

This means that the density of the disc is

$$\frac k{2rN} = \frac{xdy + O(r^2)}{2r} = x\frac{dy}{ds} + O(r).$$

As $r \to 0$, the $O(r)$ part will vanish, so we can just forget about it. Now we just need to find a more explicit expression for

$$x \frac{dy}{ds}.$$

Solving the Equation

As shown in my previous post, the curve is given by the equation

$$x(1 - y) = t.$$

Fixing $t$, we can differentiate using the product rule:

$$(1 - y)dx - xdy = 0.$$

We can rearrange this to get

$$\frac {dx} {dy} = \frac x {1 - y}.$$

Now we can calculate the density:

$$\begin{aligned} x \frac{dy}{ds} &= \frac{xdy}{\sqrt{dx^2 + dy^2}}\\[3ex] &= \frac x {\displaystyle \sqrt{\left(\frac{dx}{dy}\right)^2 + 1}}\\[7ex] &= \frac x {\displaystyle \sqrt{\frac{x^2}{(1 - y)^2} + 1}}\\[7ex] &= \frac {x(1 - y)} {\sqrt{x^2 + (1 - y)^2}}\\[3ex] &= \frac t {\sqrt{x^2 + (1 - y)^2}}. \end{aligned}$$

Don’t forget that we had shifted the diagram by $(x, y) \mapsto (x + t, y)$. So taking that into consideration, we can see that the density of a point on the original curve is given by

$$\frac t {\sqrt{(x + t)^2 + (1 - y)^2}}.$$

And that’s it!

The left image below is a list of $25,\!600$ items at $t = 0.15$. The darkness of each pixel is proportional to the number of points within a small distance of it. On the right is the theoretical curve, whose darkness set by the formula we just found.

These images don’t have a lot of contrast, so it’s not super easy to compare them. But the fact that they appear to have similar gradients gives me some confidence that the solution is correct.

That’s All, Folks

I originally thought that this would be a really hard problem to solve, but surprisingly it wasn’t too bad (…for me at least. Whether my rambling is comprehensible to anyone else is a different story.) I do wish I knew the proper way to frame this question, and it’s still a bit strange that I needed two different definitions of density. If anyone knows more about this, feel free to reach out!

Anyway, that’s all for now. Hope this was interesting!