Today's Math Lesson: Bubble-sort, anyone?

Here is a list of numbers:    7  12  5  23  11  6  14  8  .  If I asked you to sort them from smallest to largest, it would not be a difficult task.  If I gave you a longer list, say of all the players in the National League with their RBI totals so far, and asked you to sort them, it would take a lot longer, but it would not be a difficult task. In my math classes we made a big distinction between difficult and tedious. Sorting through the list would be tedious, but not difficult. Because of that, it is a perfect task to be given to a machine, such as a calculator or a computer. And in fact, sorting lists is a major job that computers do, whether alphabetically or numerically. Thus the interest on the part of mathematicians and computer scientists in sorting algorithms. An algorithm is a procedure for doing something. Some of you may remember the long division algorithm from your school days. Or if you are my age and were in honors math classes, maybe you remember an algorithm for finding the square root of a number like 27.62 using pencil and paper.   

When you try to get a machine to do something, you have to have a very detailed set of instructions to follow. You can't say, "Well, lets just look over the list and see what jumps out at us."  There are a lot of different sort algorithms out there.  And they all work at different rates based on how the list starts out. Some sorting algorithms are great if the list is not too mixed up, but take a long time for a very mixed up list. Some have difficulty deciding when they are finished.  One of the simplest is the bubble sort. Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. It is called bubble sort because the larger numbers "bubble up" to the top of the list. When the first pass is done, the largest number on the list is now in the right spot.This animation from sorting-algorithms.com gives a feeling for what bubble sort does. Click on the picture to get a stack of bars of different sizes, which will then be sorted from smallest to largest.  Notice how the bars in correct order seem to "bubble up" from the list. Hit the back button on your browser to get back to my blog.     

This may seem interesting to some of you, but I know many of you (come on - admit it) are thinking how much more interesting it would be if you could picture a bubble sort as a kind of Hungarian folk dance. Well, the folks at AlgoRythmics had the same thought. It is a long video, which gives you an idea of why bubble sort is not used much at all. It is a very inefficient way to sort a long list. Luckily here you can find other sorting algorithms (shell sort, select sort, etc.) as different folk dances. Math + dance - a natural combination.