Algorithms in Java, Parts 1-4 (3rd Edition) (Pts.1-4)
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 Figure 6.5 shows an example of the algorithm in operation.
Figure 6.5. 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.
We can speed up Program 6.14 by carefully implementing the inner loop, in much the same way as we did in Section 6.3 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 Section 6.6.
Program 6.14 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
6.30 Give an example of a file for which the number of exchanges done by bubble sort is maximized.
6.34 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!
| Top |