Sorting lists of items into order is an important problem in computer science. What most people don’t realise is that there are many possible ways to do this.
Big O Notation
But before we look at individual algorithms, I need to explain big O notation. Big O notation is a measure of the efficiency or power of a particular algorithm. If an algorithm is O(n) then increasing the number of items to be sorted from 10 to 100 also increases the time taken by the same factor of ten. But if an algorithm is O(log(n)) then increasing the number of items to be sorted from 10 to 100 only doubles the time taken, as log(10) is 1 and log(100) is 2.
Bubble Sort
The bubble sort is the beginners sorting algorithm. It works by comparing each consecutive pair of items in the list and swapping them if they are the wrong way around.
Imagine that we are sorting the following six items: 536, 362, 653, 937, 351, 331.
The first operation compares 536 and 362 and because 362 is less than 536 the two items are swapped. The second operation compares 536 and 653, and because they are already the correct way around no swap takes place.
- 536, 362, 653, 937, 351, 331.
- 362, 536, 653, 351, 331, 937.
- 362, 536, 351, 331, 653, 937.
- 362, 351, 331, 536, 653, 937.
- 351, 331, 362, 536, 653, 937.
- 331, 351, 362, 536, 653, 937.
At this point, after five run-throughs and a total of ten swaps (but many more comparisons) the list is ordered.
The bubble sort is, on average, O(n2). This means that if the number of items increases by a factor of ten from 10 to 100 then the time taken increases by a factor of one hundred. The position of items in the list is particularly important in the bubble sort. Large items at the start of the list (rabbits) quickly move to the end of the list, but small items at the end of the list (turtles) take much longer to move to the correct position.
A modification of the bubble sort, known as the cocktail shaker sort, aims to reduce the effect of turtles by alternating direction on each run, running forwards and then backwards. For this reason it is sometimes known as the bidirectional bubble sort.
Running the list above through the cocktail shaker sort requires one fewer run than the bubble sort, because 331 acts as a turtle in the previous example:
- 536, 362, 653, 937, 351, 331.
- 362, 536, 653, 351, 331, 937.
- 331, 362, 536, 653, 351, 937.
- 331, 362, 536, 351, 653, 937.
- 331, 351, 362, 536, 653, 937.