25.5. Applet Clients
23.3. Bubble Sort
The bubble sort algorithm makes several passes through the array. On each pass, successive neighboring pairs are compared. If a pair is in decreasing order, its values are swapped; otherwise , the values remain unchanged. The technique is called a bubble sort or sinking sort because the smaller values gradually "bubble" their way to the top and the larger values sink to the bottom. After first pass, the last element becomes the largest in the array. After the second pass, the second last element becomes the second largest in the array. Continue the process until all elements are sorted.
Figure 23.1(a) shows the first pass of a bubble sort of an array of six elements (2 9 5 4 8 1). Compare the elements in the first pair (2 and 9), and no swap is needed because they are already in order. Compare the elements in the second pair (9 and 5), and swap 9 with 5 because 9 is greater than 5. Compare the elements in the third pair (9 and 4), and swap 9 with 4. Compare the elements in the fourth pair (9 and 8), and swap 9 with 8. Compare the elements in the fifth pair (9 and 1), swap 9 with 1. The pairs being compared are highlighted and the numbers that are already sorted are italicized.
Figure 23.1. Each pass compares and orders the pairs of elements sequentially.
The first pass places the largest number (9) as the last in the array. In the second pass, as shown in Figure 23.1(b), you compare and order pairs of elements sequentially. There is no need to consider the last pair, because the last element in the array is already the largest. In the third pass, as shown in Figure 23.1(c), you compare and order pairs of elements sequentially except the last two elements, because they are already ordered. So in the k th pass, you don't need to consider the last k - 1 elements, because they are already ordered.
The algorithm for bubble sort is described in Listing 23.1.
Listing 23.1. Bubble Sort Algorithm
1 for ( int k = 1 ; k < list.length; k++) { 2 // Perform the kth pass 3 for ( int i = ; i < list.length - k; i++) { 4 if (list[i] > list[i + 1 ]) 5 swap list[i] with list[i + 1 ]; 6 } 7 } |
Note that if no swap takes place in a pass, there is no need to perform the next pass, because all the elements are already sorted. You may improve the preceding algorithm by utilizing this property as in Listing 23.2.
Listing 23.2. Improved Bubble Sort Algorithm
1 boolean needNextPass = true ; 2 for ( int k = 1 ; k < list.length && needNextPass; k++) { 3 // Array may be sorted and next pass not needed 4 needNextPass = false ; 5 // Perform the kth pass 6 for ( int i = ; i < list.length - k; i++) { 7 if (list[i] > list[i + 1 ]) { 8 swap list[i] with list[i + 1 ]; 9 needNextPass = true; // Next pass still needed 10 } 11 } 12 } |
The algorithm can be implemented as shown in Listing 23.3.
Listing 23.3. BubbleSort.java
1 public class BubbleSort { 2 /** The method for sorting the numbers */ 3 public static void bubbleSort( int [] list) { 4 boolean needNextPass = true ; 5 6 for ( int k = 1 ; k < list.length; k++) { 7 // Array may be sorted and next pass not needed 8 needNextPass = false ; 9 for ( int i = ; i < list.length - k; i++) { 10 if (list[i] > list[i + 1 ]) { 11 // swap list[i] with list[i + 1] 12 int temp = list[i]; 13 list[i] = list[i + 1 ]; 14 list[i + 1 ] = temp; 15 16 needNextPass = true ; // Next pass still needed 17 } 18 } 19 } 20 } 21 } |
23.3.1. Bubble Sort Time
In the best-case, the bubble sort algorithm needs just the first pass to find out that the array is already sorted. No next pass is needed. Since the number of comparisons is n - 1 in the first pass, the best-case time for bubble sort is O ( n ).
In the worst case, the bubble sort algorithm requires n - 1 passes. The first pass takes n - 1 comparisons; the second pass takes n - 2 comparisons; and so on; the last pass takes 1 comparison. So, the total number of comparisons is:
Therefore, the worst-case time for bubble sort is O ( n 2 ).
EAN: N/A
Pages: 503