The Shuttle Sort is similar to the Bubble Sort - in each pass through the numbers, we compare the
and
numbers. It is different in that if we have to swap them, indicated by dashes in the table below. We then compare the smallest of this pair with the preceding number, and swap if necessary. Each time a swap is made, we compare with the previous number. This is illustrated below for the list 7 5 2 4 10 1.
|
Pass |
Order |
|---|---|
|
1 |
7 – 5 2 4 10 1 |
|
2 |
5 7 - 2 4 10 1 |
|
5 – 2 7 4 10 1 |
|
|
3 |
2 5 7 - 4 10 1 |
|
2 5 – 4 7 10 1 |
|
|
2 - 4 5 7 10 1 |
|
|
4 |
2 4 5 7 – 10 1 |
|
5 |
2 4 5 7 10 - 1 |
|
2 4 5 7 – 1 10 |
|
|
2 4 5 - 1 7 10 |
|
|
2 4 – 1 5 7 10 |
|
|
2 - 1 4 5 7 10 |
|
|
|
1 2 4 5 7 10 |
This uses just 12 comparisons to sort our example data.
It is not until the final pass that we can be sure that any numbers are in the correct position. Also, the fourth pass contained just a single comparison, since the two numbers being compared were already in the correct order. In general the number of comparisons needed in each pass is not predictable. However, the maximum number of comparisons in the nth pass is n. We will clearly need m-1 passes for m numbers, so the maximum number of comparisons needed to put m numbers in order is:
Hence our example would need at most
comparisons. You should note that this is a worst case estimate - in general, we will need less comparisons than this.
For sorting 12 items, this algorithm would use at most
comparisons.