Algorithms are everywhere. Our children are even taught about them at school, but have you ever found yourself wondering what an algorithm actually is? Maybe you’ve thought they’re something used by computers and created by computer programmers, but don’t really know what they are?
The dictionary defines an algorithm as:
“A set of rules for solving a problem in a finite number of steps.”
Algorithms come in all shapes and sizes. They can be extremely complicated, but they can also be very simple and easy to understand.
Examples of more complex algorithms include those used to price financial products in a bank or to determine the best route between two points in a satellite navigation system. Simpler algorithms include those used to sort lists of numbers, such as Bubble Sort.
Bubble Sort
Bubble Sort is one of the easiest algorithms to understand. As its name suggests, it’s an algorithm used for sorting. Often the easiest list of things to sort are numbers. Bubble Sort works by comparing each number in the list to the number next to it and swapping them with each other if the numbers are in the wrong order. This process is performed again and again until a pass over the list requires no swaps. At this point the list is sorted. Knowing when to stop sorting the list is just as important as knowing how to sort the list. As we know when to stop (when a pass has no swaps), Bubble Sort can be used for lists of any size.
The easiest way to demonstrate Bubble Sort is with a simple example. Take the list of numbers:
3, 2, 1
We can use Bubble Sort to reverse the list. The first time we pass over the list the first two numbers are 3 and 2. 3 is greater than 2 so we swap them over:
2, 3, 1
Next we compare 3 and 1. 3 is greater than 1, so we swap them over:
2, 1, 3
There are no more pairs of numbers to compare on this pass and there were two swaps (3 & 2 and 3 & 1) so we pass over the list again. The first two numbers on the second pass are 2 and 1. 2 is greater than 1, so we swap them over:
1, 2, 3
Even though we have successfully reversed the list, we’re not finished. Next we compare 2 and 3. 2 is not greater than 3 so we don’t swap them. There are no more pairs of numbers to compare on the second pass and there was a single swap (1 & 3) so we pass over the list again.
1, 2, 3
The first two numbers to compare are 1 and 2. 1 is not greater than 2, so we don’t swap them. Then we compare 2 and 3. 2 is not greater than 3 so we don’t swap them. There are no more pairs of numbers to compare on the third pass and there were no swaps so we’ve finished and successfully reversed the list.
Sorting Algorithms in the Real World
Bubble Sort is taught to trainee software engineers as it’s easy to understand and implement. However, it’s rarely actually used in the real world as it’s inefficient and there are other more efficient sorting algorithms, such as Quicksort, which are only a little more difficult to understand implement.
Sorting occurs in all sorts of systems in the real world. One example is in the software used to sort mail into the order a postman will deliver it as he walks along his round. Postcodes and other address elements are read into the system and sophisticated algorithms used to sort the mail into the correct order.
The next time someone mentions algorithms to you, remember it’s a set of rules for solving a problem in a finite number of steps.