Bubble sort

Suppose you want to buy a new phone accessory online. You go to a search site and it finds 100 retailers stocking the accessory, and offers to sort them by price. Or you’ve got a list of 1000 names on a spreadsheet which you want to sort alphabetically. Have you ever wondered how a computer carries out a sort?

Such a problem can be solved using an algorithm which is simply a set of simple, unambiguous instructions which will lead to a solution. Algorithms often include a loop back to a previous instruction. Put simply, one line of the algorithm may say something like: “Have you got to the solution yet? If yes, finish. If no, go back to instruction 3”. Every pass through the algorithm is called an iteration, and the aim of all algorithms – which can often be graphically illustrated by a flowchart – is to get to the solution as efficiently as possible, and with as few iterations as possible.

Algorithms like this form part of a subject called decision mathematics, and the many problem-solving techniques have huge applications in everyday life. Satnavs use algorithms to find the shortest or fastest route from A to B; construction sites use project management tools such as critical path analysis and Gantt charts to keep the building work on budget and on time; delivery companies need to work out the shortest route for a driver to visit a set of drop-off points, and then get back to base; a large department might use a matching algorithm to find the best way to allocate tasks to people so that each task can be carried out by a suitably qualified worker.

So what about our sorting problem. If you were given a list of numbers to sort by hand you would probably look down the list for the smallest, write it down, then look for the next smallest and so on. But this is incredibly inefficient: imagine a computer doing the same thing for a list of 10,000 numbers. The program would have to work through the complete list 10,000 times before the sort was completed. There are many sorting algorithms: here’s one called the “Bubble Sort”.

Step 1:    Start at the beginning of the list.
Step 2:    Pass through the list and compare adjacent values. For each pair:
If they are in order, leave them alone
If the second is smaller than the first, swap them over.
Step 3:    When you reach the end of the list:
If you have done any swaps, go back to step 1
If you haven’t done any swaps, the list is now in order. Stop.

Here’s the bubble sort working on the list 30  18  50  9  16  42. The table below shows the whole of pass 1 with highlighted cells indicating which pair is being compared. You can see that the largest number moves to the end of the list like a bubble in a glass of champagne!

Subsequent passes result  in:

Pass 2:    18  9  16  30  42  50
Pass 3:    9  16  18  30  42  50

When pass 4 is run there will be no swaps, so the list is in order.

It may seem complicated, but a computer will sort 10,000 numbers very fast using this method, particularly if the numbers are roughly in order to start with (fewer swaps needed). Other sorting algorithms can be used in different situations.