Page excerpted from Sort topic of a first year course in Structured Programming

## Bubble Sort

Here's the code for a bubble sort. Unlike the others, we've run it backwards so you can see the smallest values bubble upwards. We can get a pseudo animation by running it in the Teaching Machine and then cycling through the loop in `bubbleSort` without stepping into `bubblePass`.

Code Notes

1. The TM doesn't support array initialization yet so put the cursor on the line with the call to `bubbleSort`, then hit the stepToCursor button ().

2. Step into() `bubbleSort` and click twice more to load `anArray` and `n` into memory.

3. `anArray` is just a reference to `array`. Go to the memory and click on the expander for the original `array` to see its data.

4. Put the cursor on the call to `bubblePass` and click on toCursor button, then click on stepOver(). The smallest value in `array` should "bubble" to the top.

5. Repeat these two steps and the next smallest value should bubble to the second position. Again and the third smallest goes to the third position. Each time this is done `i` is increasing and the `bubblePass` is being carried out on a smaller and smaller subset of `array`.

6. Now step into `bubblePass` to see how it works (you may have to expand `array` again to see it). Notice how it starts at the bottom and works upward, pushing the smallest value to the current `top` as it goes.

Note: The inner sort has been delegated to the `bubblePass` function both to improve the animation and also to re-inforce the previous work on delegation, The code would run faster if it were combined into a single function, which is what would normally be done. Of course, no-one interested in efficiency would use a bubble sort anyway!

## An Improved Bubble Sort

The swapping that is constantly being done in the subarrays means that, very often, the remaining subarray is already sorted. The bubble sort blindly keeps going.

Here the `bubblePass` routine indicates if it did any swaps at all. If it didn't the subarray is sorted and `bubbleSort` quits.

## Selection Sort

Instead of swapping our way through the sub-array, the selection sort merely moves through the sub-array looking for the smallest value. Thus, for a sub-array starting at `i`, it does `n-i-1` comparisons but no swaps. At the end of the search, the smallest value is swapped with the value at position `i`. Thus the selection sort does at most`n-1` swaps.

Again, delegation is used for illustration. Normally efficiency would dictate the functions be combined because function calls are expensive.

# Examples Shown in Full