N-SEA Documentation: Bubble Sort

The BubbleSort macro implements the bubble-sort algorithm. This makes repeated passes through a list of names or numbers, swapping adjacent items if they are in the wrong order. It terminates when a pass produces no changes in the order of the list.

If we consider the problem of sorting integers into ascending order and the data is:

100 2 4 6 8 20

then it is easy to see that at the end of the first pass that the '100' is in its correct position. At the end of the second pass the '20' will be in the correct position. In general after k passes k elements are in their correctly sorted position, so we don't need to make the comparisons in those positions.

Whilst the algorithm will terminate if no changes are made, it can be quite slow. If the data to be sorted had instead consisted of

100 2 4 6 8 1

then we can see that it would take 5 passes to move the 1 to the head of the list. This amounts to 15 comparisons. In general if a list contains N elements then a maximum of 0.5*N*(N+1) comparisons may be necessary.

To sort some data, open the BubbleSort algorithm from the 'Decision' menu under the N-SEA menu. The following dialogue box appears:

Click on the 'Data to be sorted' box and then select the data on the worksheet. Choose whether you want the data to be sorted in ascending or descending order. The default is to sort into ascending order. Finally click on the 'Locate top left hand cell of answer at' box and select a cell on the worksheet that will be the top left hand cell of the calculation. The macro can write many cells to the worksheet, so it is advisable to choose a cell that has many clear cells underneath.

You may display the help file or cancel the macro by pressing the appropriate button. When you press the 'OK' button a small message box appears:

This repeats the options chosen and gives you an opportunity to change your options, cancel the macro or continue with the calculation.

When you press the 'Yes' button, further information is relayed.

On pressing the 'OK' button a further dialogue box appears.

This gives you the option of bringing up the Help system, stepping through the algorithm or computing the solution directly.

You might decide to proceed to the 'Next Step' and then a dialogue box and output is displayed as follows:

Whether you step through the algorithm or elect to press the 'Finish' button the final solution is displayed on the worksheet, just where you requested.

A typical answer is displayed below.

© Numerical Algorithms Group

Visit NAG on the web at:

www.nag.co.uk (Europe and ROW)
www.nag.com (North America)
www.nag-j.co.jp (Japan)

http://www.nag.co.uk/n-sea/docs/bubblesort.asp