Sort Algorithms: Part 1

This article was originally published in The Crypt Mag

This is the first in a series of tutorials on the wonderful world of sort algorithms. In this series we will be looking at a number of different methods of sorting data and the advantages and disadvantages of each.

This tutorial assumes that you have at least some knowledge of programming.

So, what is a sort algorithm anyway?

Simply put, a sort algorithm is a routine that organises data into some kind of order.

Examples of this are programs that keep a list of names and addresses or video games that keep a hi-score table. It would not be much use if your list of e-mail contacts was in any old order so that finding a particular person was difficult. Also, it would not be much fun if you had just achieved your all-time personal best in your favourite game only to have your hi-score displayed at the bottom of the table instead of its rightful place at the top! Yes, sort algorithms can be very useful things indeed!

The first sort algorithm that we will be looking at is what is known as a bubble-sort.

To illustrate how this algorithm works, imagine that we have a list of numbers:

5
3
7
4

As you can see, these are not in any particular order.

The bubble-sort looks at the first two numbers and decides if the first number is higher or lower than the second number. If the first number is higher the bubble-sort will swap the two numbers about.

In this case the first number is indeed higher than the second number; the first number 5 being higher than the second number 3. So, the bubble-sort swaps the numbers about and the list ends up like this:

3
5
7
4

Next the bubble-sort looks at the second and third numbers. In this case the second number 5 is lower than the third number 7 so there is no need to swap the numbers.

With the third and fourth numbers the 7 is higher than the 4 so these are swapped to give:

3
5
4
7

Once at the end of the list the bubble-sort goes back to the top and repeats the swapping process if any number is higher than the next one down the list until no further swaps can be made.

Going through the list again we can see that the second and third numbers need to be swapped. This gives us:

3
4
5
7

It should be obvious that the list of numbers is now in ascending order. If the bubble-sort were to run through the list again no swaps would be made so the bubble-sort knows that its job is done.

If you look closely at how the algorithm actually works you will see that the numbers ‘bubble’ up until they are in the correct order, hence why it is called a bubble-sort.

Here is the algorithm in pseudo-code:

   Begin BUBBLESORT
      Repeat
         Set SWAP flag to false
         For N=1 to maximum number of items in list
            Is entry at position N higher than entry at position N+1?
               If so, then swap numbers and set SWAP flag to true
         Next N
      Until SWAP flag is false
   End BUBBLESORT

It is worth noting here that if you want the bubble-sort to sort in a descending order all that you have to do is perform the swap if the number at position N is lower than the one in position N+1.

The advantages of the bubble-sort is that it is relatively easy to program and uses a minimum amount of memory. The disadvantage of the bubble-sort is that it can be painfully slow when dealing with a large number of items in a list. The ideal places to use this algorithm are where there are a small number of items in the list (e.g. a hi-score table in a game) or where memory constraints are an issue.

In the next tutorial I’ll be showing you how you can improve the bubble-sort to speed things up.

Article copyright © 2001, 2009 Francis G. Loch

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Homepage of Francis G. Loch's various projects

%d bloggers like this: