Simple Ideas of Algorithms
You need to be able to know and use the following algorithms to sort numbers, letters etc. into a certain order:
Bubble Sort
- Start on LHS, compare 1st two numbers, swap if necessary.
- Compare next two numbers, swaps if necessary. And so on until the end.
- Stopping condition: No swaps have occured in the pass, algorithm stops.
Remember!
You must show every stage including the last pass in which no swaps are made. Otherwise you will lose marks because you are not following the algorithm.
I also put a box around the number(s)/letter(s) at the end which, in effect, I have isolated because
they are they largest and will not be swapped again. This gives a stairway effect when you draw it out (see e.g. below).
e.g. To sort 4, 7, 13, 26, 8, 15, 6, 56 into ascending order:
- After 1st pass: 4, 7, 13, 8, 6, 15, 26, 56
- After 2nd pass: 4, 7, 8, 6, 13, 15, 26, 56
- After 3rd pass: 4, 7, 6, 8, 13, 15, 26, 56
- After 4th pass: 4, 6, 7, 8, 13, 15, 26, 56
- After 5th pass: 4, 6, 7, 8, 13, 15, 26, 56
Therefore, the sorted list = 4, 6, 7, 8, 13, 15, 26, 56
Shuttle Sort
- Compare the 1st and 2nd numbers, and if necessary swap.
- Compare the next two numbers, if necessary swap. If a swap is made, you go back and compare the two previous numbers and so on.
Note: Underline the two numbers you are initially comparing to make it clear.
Remember!
Rewrite the numbers you are asked to sort so you can underline the two numbers you are initially comparing
e.g. To sort 5, 1, 2, 6, 9, 4, 3 into ascending order:
- To sort: 5, 1, 2, 6, 9, 4, 3
- 1st pass: 1, 5, 2, 6, 9, 4, 3
- 2nd pass: 1, 2, 5, 6, 9, 4, 3
- 3rd pass: 1, 2, 5, 6, 9, 4, 3
- 4th pass: 1, 2, 5, 6, 9, 4, 3
- 5th pass: 1, 2, 4, 5, 6, 9, 3
- 6th pass: 1, 2, 3, 4, 5, 6, 9
Therefore, the sorted list = 1, 2, 3, 4, 5, 6, 9
Shell Sort
- Think of the list of numbers as a vertical column, then halve the number of rows and sort each row
- Repeat! [ignore remainders. e.g. 5/2 = 2]
- Stop after you have sorted the numbers when there is one row left
N.B. The sorting of each row would be done using Shuttle Sort (most probably), but you do not have
to show your workings for Shuttle Sort in the exam if the question says use Shell Sort.
e.g. To sort 5, 9, 1, 3, 0, 6, 8 into ascending order:
- As a column, it has 7 rows. 7/2 = 3 rows: (see table)
| 5 |
3 |
8 |
→ |
3 |
5 |
8 |
| 9 |
0 |
|
→ |
0 |
9 |
| 1 |
6 |
|
→ |
1 |
6 |
(The arrows denote sorting the rows into ascending order)
- Halve number of rows: 3/2 = 1 row: 3, 0, 1, 5, 9, 6, 8
- Using shuttle sort: 0, 1, 3, 5, 6, 8, 9
Therefore, the new order = 0, 1, 3, 5, 6, 8, 9
Quicksort
- Take the first element as the pivot.
- Create 2 sublists either side of the pivot - for those greater and smaller than the pivot. Make sure you keep them in the same order.
- Repeat process on each sublist.
- Stopping Condition: When a sublist is empty or only has one element.
e.g. To sort: 6, 3, 9, 8, 2, 7, 1, 5, 4 into ascending order (see table):
| To sort: |
6 |
3 |
9 |
8 |
2 |
7 |
1 |
5 |
4 |
| 1st pass: |
3 |
2 |
1 |
5 |
4 |
6 |
9 |
8 |
7 |
| 2nd pass: |
2 |
1 |
3 |
5 |
4 |
6 |
8 |
7 |
9 |
| 3rd pass: |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
- The pivot(s) to be used for the next pass are highlighted with a dashed box.
- The pivot(s) which have been used in previous passes are highlighted with a solid box.
Therefore, the sorted list = 1, 2, 3, 4, 5, 6, 7, 8, 9
The maximum possible number of comparisons and swaps that would need to be made for a list of 'n' numbers, for each
of these algorithms is the triangular number formula: 0.5n(n-1)