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

Obligatory "First post!"

Hi and welcome to my tech oriented blog, where I will post updates about my own projects (mostly about electronics and programing, sometimes even both) and occasionally a few tech rants (and a few non-tech rants). I'm not a blog oriented person (every blog I start tends to evaporate in a few weeks), but I will do my best to post fairly regularly.
Now, some more concise stuff I will be writing about: I am in the process of buying a new soldering iron and some other stuff, like a loupe with a third hand and a PCB etching kit, mostly because:

1. My old soldering iron got clogged (I had a gas one, the worst 20e ever spent)
2. I need to make some quick repairs around the house, for which I require a soldering iron
3. I also want to get more into electronics (the practical kind, hence the projects) and
4. I bought a Stellaris Launchpad while it was on preorder (nifty gadget, check it out )

 So, stick around, have a few beers, and wait for the first real post in the following weeks.