SORTING - Introduction to Java Programming: Comprehensive Version - page 865

Figure 23.3a shows the first pass of a bubble sort on 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), and swap 9 with 1. The pairs being compared are highlighted and the numbers
already sorted are italicized in Figure 23.3.

bubble sort illustration

bubble sort on the
Companion Website

25 89 41 21 89 4 5 1489 25

2581 94 241 9 58

2 4 5 8 1 9
2 4 5 8 1 9
2 4 5 1 8 9

25 89 41

2 5 9 4 8 1
2481

2 1 489 5

59
2491

21 89 4 5

58
241 9

58

(a) 1st pass (b) 2nd pass (c) 3rd pass (d) 4th pass (e) 5th pass

F IGURE 23.3

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.3b, 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.3c, you compare and order pairs of elements sequentially
except the last two elements, because they are already in order. 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 a bubble sort is described in Listing 23.2.

-

algorithm

L ISTING 23.2

Bubble Sort Algorithm
1 for ( int k = 1 ; k < list.length; k++) {
2 // Perform the kth pass
3 for ( int i = 0 ; 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 can use this property to improve the algorithm in Listing
23.2 as in Listing 23.3.

L ISTING 23.3

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 = 0 ; 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 }