Today I had a very simple problem in one of my Golang side projects. I have a server that retrieves a JSON array of objects that have the same schema and I want to display them in a server side rendered HTML table on a web page¹. If I had unlimited time, I would probably have started a Create-React-App project and stick in a popular table library that takes care of rendering this JSON object. However, that workflow requires building the Single Page App and then I probably have to embed it in the server. That’s a bit too much effort for me as I wanted something more php-esque.

Rendering the table by hand wasn’t too bad. What wasn’t great was the lack of features that I’ve grown to expect from HTML tables: column sorting, filtering, resizeable column etc. I had an immediate need for sorting by column and since I’ve already invested in sever side rendering I decided to look for a solution in javascript without using React library.

I found this page on w3 that basically implements the sort from first principle. What caught my attention was that it was using bubble sort, (kind of)! I’ve always thought bubble sort was something only referenced in academia and not in practise. I suppose this was chosen because the optimization from sorting separately and then redrawing the whole DOM is negligible than just doing tiny mutations.

I then wondered about the number of comparisons and swaps that needed to happen when performing bubble sort.

In a reverse sorted list of size n, how many comparisons must be done when performing bubble sort?

If you like to have a go. Stop reading and come back when you have a solution.

The theoretical answer is n*(n+1)/2 because the first n comparisons will fix one number and we’ve reduced it to the n-1 case.

I was curious of theory matched practise so I opened the link to a JS code editor on the same where I could edit the code. I added a counter variable to the function and counted number of comparisons done. For a list of 8 numbers, it had to do 84 comparisons. Wait a minute. This isn’t the same as the computed value of 36!

On closer inspection, the algorithm given on the page is actually a rather inefficient bubble sort! The main reason is that it breaks out of the first loop so as soon as it found something to swap, it forgets its state in the traversal and has to recompare from scratch.

Tweaking the number of items in the list, I noticed the following number sequence for the number of comparisons done:

1, 4, 10, 20, 35, 56, 84

If the pattern for generating this sequence is not obvious, taking the differences between the terms reveals the following sequence.

1, 3, 6, 10, 15, 21, 28

This one is the partial sum of the counting sequence, aka triangular numbers. i.e

1, 1 + 2, 1 + 2 + 3, …

Which means the original sequence is a partial sum of the triangular number sequence! Interestingly, entering this sequence onto the encyclopedia of number sequence reveals that this is also known as tetrahedral numbers!

The n^2 solution

After realizing the one given is worse than bubble sort, I tried to fix it and the following is my solution:

function swap(i, rows) {
      rows[i].parentNode.insertBefore(rows[i + 1], rows[i]);
}

function sortTable(hasSwitched) {
	// Try one order
	didSwitch = aux(function (a, b) { return a > b })
	if (!didSwitch) {
    // try the other order
    	aux(function (a, b) { return a < b })
    }
}

function aux(compare) {
  var table, rows, x, y;
  table = document.getElementById("myTable");
  rows = table.rows;
  var hasSwitched = false;
  
  for (i = 1; i < (rows.length - 1); i++) {
    for (j = 1; j < (rows.length - i); j++) {
      x = rows[j].getElementsByTagName("TD")[0];
      y = rows[j + 1].getElementsByTagName("TD")[0];
      if (compare(x.innerHTML.toLowerCase(), y.innerHTML.toLowerCase())) {
        swap(j, rows)
        hasSwitched = true
      }
    }
  }
  return hasSwitched
}