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.
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.
Quick Sort
First, the median is selected as a pivot, by calculating (n+1)/2, where n is the number of items in the initial list. The median is then designated in some way, by circling it, for instance.
A single pass is then done through the list, putting everything with a value < median before the median, and everything with value > median after it. The items should not move other than away from items above/below the median (whichever they are not).
The median should then stick still, and it's designation be changed to something else to avoid confusion (perhaps, a square).
A new median should now be found for the list of items each side of the original median. The above steps should be followed for each side.
This process should be repeated until each item has been the median, and the list will be sorted when each item has a square around it (or whatever designation you have chosen).
Example
Sort: 2,6,3,9,5,7,8,4 using the Quick Sort algorithm.
(Italics denotes a new pivot, and bold denotes an 'old' (now fixed) pivot).
2,6,3,9,5,7,8,4
2,3,4,5,6,9,7,8
2,3,4,5,6,7,9,8
2,3,4,5,6,7,8,9
2,3,4,5,6,7,8,9
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 kn2 for some constant k.
