From The Student Room

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Sorting Algorithms

---

Contents 1 Bubble Sort 2 Shuttle Sort 3 Efficiency 4 Also See 5 Comments

Bubble Sort

1. If there is only one item in the list, stop.
2. Make one pass through the list: compare the first and second items in the list and swap if the second is smaller than the first, compare the seconds and third items in the list and swap if the third is smaller than the second etc. etc.
3. If no swaps have occurred, stop. Otherwise make the last item permanent and form a new shorter list with the last item removed. Return to step 1 to do another pass.

You may be required to count the number of comparisons and swaps you do in each pass.

Here is an example:

Shuttle Sort

• First pass: Compare first and second items and swap if necessary.
• Second pass: Compare second and third items and swap if necessary. If a swap has occurred, compare the first and second items and swap if necessary.
• Third pass: Compare the third and fourth items and swap if necessary. If a swap has occurred, compare the second and third and swap if necessary. If a further swap has occurred here, compare the first and second again and swap if necessary.
• Repeat through the whole list.

The effect of pass n is to pick up item in position n + 1 and insert it in the correct place in the already sorted sublist of the first n items.

Shuffle sort cannot be terminated early. The number of passes is always one less than the length of the original list.

Efficiency

We usually measure the efficiency of an algorithm by considering the worst case scenario. For both bubble sort and shuffle sort, this is when the list is in reverse order.

In this case, both algorithms use 1 + 2 + 3 + ... + (n-1) comparisons and swaps.

Both algorithms are quadratic order because the measure of efficiency is a quadratic function of the size of the list.

For a very large problem, the quadratic term would dominate and the run time would be approximately kn² for some constant k.

Also See

See the other D1 notes:

1. Algorithms
2. Sorting algorithms
3. Packing algorithms
4. Graphs and networks
5. Minimum connector problems
6. The shortest path
7. Route inspection
8. The travelling salesman problem
9. Linear programming
10. The simplex algorithm

Comments