Sunday, November 13, 2011

Bubble Sort

Bubble sort is the crappiest sorting algorithm out there. For the longest time I found it perplexing why it was taught in school, when insertion sort and selection sort are more intuitive, (slightly) more efficient, and easier to implement. Researchers mentioned in the Wikipedia page find it mind-boggling as well.

Then bubble sort came up in the most unlikely circumstances, in Galois theory, when proving that the roots of the polynomial x^5+15x+5 cannot be written using +, -, *, / and radicals (taking the n-th root). The key idea is that one can sort a list when equipped with two operations: rotating the entire list, and flipping two elements (at fixed indices).

This means that one can also obtain any permutation of a list using the same two operations. The fact that this can be done isn't difficult to show, but it isn't immediately obvious either (at least to me).

So the takeaway is this: bubble sort tells us that it is possible to permute a list by means of rotation and flipping two elements.

End of Entry