An algorithm is a procedure or set of precise instructions, which can be followed to solve a problem.
The instuctions in an algorithm must be precise, there must be no ambiguity in any instruction, nor any ambiguity as to which instruction is next.
An algorithm must solve a problem and do so within a finite number of instructions and so must include an instruction to stop.
If a set of instructions does not follow these rules it is not an algorithm.
Sorting Algorithms[]
To sort a list in ascending or descending order an algorithm must be used. There are a number of sorting algorithms that can be used. In the exam it is likely that you will be asked to describe how these algorithms work and use them to manually sort a list. It is important that you show every step of your workings (unless asked otherwise) even if you could easily sort the whole list in your head.
Bubble-sort[]
- Starting at one end of the list, adjacent pairs of list items are compared and if they are in the wrong order they are swapped.
- This is repeated until the end of the list is reached.
- The whole process is then repeated until a pass through the list produces no swaps.
In the following example the list is sorted in ascending order. The two items being compared are circled. On the first pass the highest number ends in its correct position, on the second pass the second highest does and so on. As these items will not change position again their comparison are no longer show.
Quick-sort[]
The quick-sort algorithm is a more efficient sorting algorithm as it requires fewer comparisons.
For this method the midpoint of the list (and any later sublists) must be identified. While the midpoint for a list with an odd number of items is easy to work out it is more difficult when there are an even number of items.
For example in a list with 5 items the 3rd item will the midpoint with two items either side of it. However if the list had 4 items either the 2nd or the 3rd item may be used. As long as you are consistent it is okay to use either.
One convention for choosing the midpoint is to use [(N+1)/2] where N is the number of items in the list. Note that the square brackets (‘[]’) indicate that the answer is to be rounded to the nearest integer (whole) value.
For example for the list of 5 items this would be [(5+1)/2] = [6/2] = 3; the 3rd item (as we assumed earlier). For the list of 4 items this would be [(4+1)/2] = [5/2] = [2 ½] = 3; also the 3rd item.
The quick-sort algorithm is as follows:
- Select an item from the list to be used as a pivot. (Any number can be used as long as you are consistent, for these examples the midpoint has been used.)
- Rearrange the list placing those numbers less than the pivot on the left (if sorting in ascending order; right otherwise) and those greater than the pivot on the right (left for descending). Other than this the numbers must be left in the same order.
- A sublist has now being created on either side of the pivot. Repeat this process on each sublist and so on until each sublist has only one item. The list is now sorted.