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