Previous   Next

Bubble Sort

The first sort that many people learn, because it is so simple, is bubble sort: Keep passing through the file, exchanging adjacent elements that are out of order, continuing until the file is sorted. Bubble sort's prime virtue is that it is easy to implement, but whether it is actually easier to implement than insertion or selection sort is arguable. Bubble sort generally will be slower than the other two methods, but we consider it briefly for the sake of completeness.

Suppose that we always move from right to left through the file. Whenever the minimum element is encountered during the first pass, we exchange it with each of the elements to its left, eventually putting it into position at the left end of the array. Then on the second pass, the second smallest element will be put into position, and so forth. Thus, N passes suffice, and bubble sort operates as a type of selection sort, although it does more work to get each element into position. Program 6.14 is an implementation, and Screenshot shows an example of the algorithm in operation.

Screenshot Bubble sort example

Small keys percolate over to the left in bubble sort. As the sort moves from right to left, each key is exchanged with the one on its left until a smaller one is encountered. On the first pass, the E is exchanged with the L, the P, and the M before stopping at the A on the right; then the A moves to the beginning of the file, stopping at the other A, which is already in position. The ith smallest key reaches its final position after the ith pass, just as in selection sort, but other keys are moved closer to their final position as well.

Java graphics 06fig05.gif


We can speed up Program 6.14 by carefully implementing the inner loop, in much the same way as we did in for insertion sort (see Exercise 6.34). Indeed, comparing the code, Program 6.14 appears to be virtually identical to the nonadaptive insertion sort in Program 6.1. The difference between the two is that the inner for loop moves through the left (sorted) part of the array for insertion sort and through the right (not necessarily sorted) part of the array for bubble sort.

Program 6.14 uses only compExch instructions and is therefore nonadaptive, but we can improve it to run more efficiently when the file is nearly in order by testing whether no exchanges at all are performed on one of the passes (and therefore the file is in sorted order, so we can break out of the outer loop). Adding this improvement will make bubble sort faster on some types of files, but it is generally not as effective as is changing insertion sort to break out of the inner loop, as discussed in detail in .

Bubble sort

For each i from l to r-1, the inner (j) loop puts the minimum element among the elements in a[i], ..., a[r] into a[i] by passing from right to left through the elements, compare–exchanging successive elements. The smallest one moves on all such comparisons, so it "bubbles" to the beginning. As in selection sort, as the index i travels from left to right through the file, the elements to its left are in their final position in the array.

static void bubble(ITEM[] a, int l, int r) { for (int i = l; i < r; i++) for (int j = r; j > i; j--) compExch(a, j-1, j); } 


Exercises

Java graphics icon01.gif 6.29 Show, in the style of Screenshot, how bubble sort sorts the sample file E A S Y Q U E S T I O N.

Give an example of a file for which the number of exchanges done by bubble sort is maximized.

ScreenshotIs bubble sort stable?

Explain how bubble sort is preferable to the nonadaptive version of selection sort described in Exercise 6.28.

Java graphics roundbullet.gif 6.33 Do experiments to determine how many passes are saved, for random files of N elements, when you add to bubble sort a test to terminate when the file is sorted.

Develop an efficient implementation of bubble sort, with as few instructions as possible in the inner loop. Make sure that your "improvements" do not slow down the program!


Previous   Next
Comments