Bradley N. Miller, David L. Ranum, Roman Yasinovskyy, J. David Eisenberg
Section5.7The Bubble Sort
The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item bubbles up to the location where it belongs.
Figure 5.7.1 shows the first pass of a bubble sort. The shaded items are being compared to see if they are out of order. If there are items in the list, then there are pairs of items that need to be compared on the first pass. It is important to note that once the largest value in the list is part of a pair, it will continually be moved along until the pass is complete.
At the start of the second pass, the largest value is now in place. There are items left to sort, meaning that there will be pairs. Since each pass places the next largest value in place, the total number of passes necessary will be . After completing the passes, the smallest item must be in the correct position with no further processing required. Listing 5.7.2 shows the complete bubble_sort function. It takes the list as a parameter and modifies it by exchanging items as necessary.
The following example shows the complete bubbleSort function working on the preceding list. We have put System.out.printf calls in the code so you can see how it works.
To analyze the bubble sort, we should note that regardless of how the items are arranged in the initial list, passes will be made to sort a list of size .Table 5.7.3 shows the number of comparisons for each pass. The total number of comparisons is the sum of the first integers. Recall that the sum of the first integers is . The sum of the first integers is , which is . This is still comparisons. In the best case, if the list is already ordered, no exchanges will be made. However, in the worst case, every comparison will cause an exchange. On average, we exchange half of the time.
A bubble sort is often considered the most inefficient sorting method since it must exchange items before the final location is known. These “wasted” exchange operations are very costly. However, because the bubble sort makes passes through the entire unsorted portion of the list, it has the capability to do something most sorting algorithms cannot. In particular, if during a pass there are no exchanges, then we know that the list must be sorted. A bubble sort can be modified to stop early if it finds that the list has become sorted. This means that for lists that require just a few passes, a bubble sort may have an advantage in that it will recognize the sorted list and stop. Listing 5.7.4 shows this modification, which is often referred to as the short bubble.
The break statement in line 23 does what its name says; it breaks out of the loop. In general, one of the authors recommends avoiding the use of break and using compound conditions instead to determine when the loop ends.
Suppose you have the following list of numbers to sort: <br> [19, 1, 9, 7, 3, 10, 13, 15, 8, 12] which list represents the partially sorted list after three complete passes of bubble sort?