Algorithm of the week: Bubble sort (and sorting in general)

Instead of studying for a test tomorrow, I'll procrastinate usefully by refreshing my memory on bubble sort and sorting in general. Not a bad way to evade studying?

So, sorting is a process where a sequence of numbers gets rearranged into either a rising progression or into a falling progression (I do not know the correct terms, but you'll understand it in a bit).

Imagine you have a sequence of numbers: 3 7 2 4 9 1
If you would sort it to be a rising progression, it would look like this: 1 2 3 4 7 9
And if you would sort it to a falling progression, it would look like this: 9 7 4 3 2 1

Humans are naturally good at sorting numbers, but what happens with computers? What happens when we have a boatload of numbers that we (humans) can't sort easily? That's where sorting algorithms come.

A sorting algorithm is a set of instructions given to the computer with the intent to sort a sequence of numbers. Since we are talking about computers, there are lot ways to accomplish sorting, some more efficient with small sequences of numbers, and some more efficient with bigger sequences of numbers. Algorithm efficiency is defined as a property that tells us how the algorithm "responds" with increased input (in this case more numbers). I will dedicate a post in full about that (and the infamous Big O notation) in the course of a few days.

Now, enough theory, time to get our hands dirty: one of the most popular sorting algorithms is the bubble sort. It's called that way because numbers tend to "float to the surface" when you use it. The case for using bubble sort for a sequence of numbers that you want to be a rising progression is like this:

1. Compare two numbers in sequence
2. If the one on the left is greater than one the right, switch places
3. If the one on the left is lower than the one on the right, do nothing
4. Go back to step one, except now compare the second number in sequence and the one after it

See? Nothing special, but very useful. Here's an example with a sequence of four numbers:

1. 3 1 7 2
2. 1 3 7 2
3. 1 3 7 2
4. 1 3 2 7
5. 1 3 2 7
6. 1 3 2 7
7. 1 2 3 7
8. 1 2 3 7

Let's break it down:

• On the first line we compared the first two numbers and concluded that the first one is lower than the second one
• On the second line we wrote the conclusion from the first step and compared the second number and the third one, from which we concluded that they don't need to be re-arranged
• On the third line we compared the third and fourth number and concluded that the third one is higher than the second one
• On the fourth line we wrote the conclusion from the previous step. We don't have any numbers to compare our fourth one to: we have reached our first pass-through. Bubble sort can have a minimum of two pass-thoroughs: the first one to sort the sequence, and the second one to verify that no more numbers can be swapped.
• On the fifth line we note that the first number is greater than the second one so we don't do anything
• On the sixth line we conclude that the second number is higher than the third one, so we are going to swap them on the next line
• On the seventh line we swap the numbers from the line before
• And finally, we pass through the sequence without swapping, which means our sequence is sorted.

 Bubble sort is one of the most basic sorting algorithms, but it is only good for sorting small sequences of numbers and for learning the basics of sorting or when you need a quick and dirty way to sort something.

Sources:
http://en.wikipedia.org/wiki/Bubble_sort
http://stackoverflow.com/questions/276113/what-is-a-bubble-sort-good-for
http://en.wikipedia.org/wiki/Sorting_algorithm