## The Shuttle Sort Algorithm

The Shuttle Sort is similar to the Bubble Sort - in each pass through the numbers, we compare theandnumbers. 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 mostcomparisons. 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 mostcomparisons.