One-dimensional Particle Physics and BubbleSort

I recently perused Donald Knuth’s website and saw that he once had a lecture called Constructing bubblesort at random: one-dimensional particle physics. As a physicist and software engineer, I naturally found this interesting. So, I thought I’d play with it.

The code

One of the papers Knuth links to on the site for his talk gives the following instructions:

Start with infinitely many 1s followed by infinitely many 0s; then randomly interchange adjacent elements that are out of order.

The code in my Github repo is modeled after those instructions and what is in Knuth’s lecture. Basically, start with a chain of 1s and 0s, as specified below, sort them at random. It also tells you:

  • How many random swaps it takes to sort the list
  • The distribution of 1s and 0s (histograms), in case you want to plot them

Ok, great. But how does this relate to particle physics?

The physics connection

The physics connection becomes a bit more clear if you imagine a 1D lattice, where the 1s are particles and the 0s are vacancies. Now, pick any site k and ask how many particles are to the right of site k. Call the result R_k. The number of 0s to the left of site k is L_k. Note that if k=N/2, then R_k=L_k.

It might be interesting to track how R_k and L_k change with “time”. Here, time means the number of random swaps needed to sort the list. For a long lattice, it might also be interesting to compute the distribution of 1s or 0s as a function of lattice site index. Then we could watch it change from all 1s on the left to all 1s on the right. Might look like a Heaviside Step Function inverting bit by bit.

Knuth specifically connects this toy problem to Young Tableaux, which are a way of describing the representations of certain groups (some of which are relevant to particle physics). My code doesn’t really go into any of this. I thought the things in the above paragraphs were more interesting.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s