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

The algorithm can be implemented in Listing 23.4.

L ISTING 23.4

BubbleSort.java
1 public class BubbleSort {
2 /** Bubble sort method */

3 public static void bubbleSort( int [] list) {

4 boolean needNextPass = true ;

5
6 for ( int k = 1 ; k < list.length && needNextPass; k++) {
7 // Array may be sorted and next pass not needed
8 needNextPass = false ;
9 for ( int i = 0 ; 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
22 /** A test method */
23 public static void main(String[] args) {
24 int [] list = { 2 , 3 , 2 , 5 , 6 , 1 , -2 , 3 , 14 , 12 };
25 bubbleSort(list);
26 for ( int i = 0 ; i < list.length; i++)
27 System.out.print(list[i] + " " );
28 }
29 }

perform one pass

-2 1 2 2 3 3 5 6 12 14

In the best case, the bubble sort algorithm needs just the first pass to find 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 a bubble sort is O(n) .
In the worst case, the bubble sort algorithm requires n

bubble sort time complexity

- 1 passes. The first pass makes

n 2 comparisons; and so on; the last pass

makes 1 comparison. Thus, the total number of comparisons is:

- 1 comparisons; the second pass makes n -

( n - 1) + ( n - 2) + g + 2 + 1

n 2
2

( n - 1) n n

2 =

O ( n 2 ) = = -

2

Therefore, the worst-case time for a bubble sort is O ( n 2 ).

23.4

✓ ✓

Describe how a bubble sort works. What is the time complexity for a bubble sort?

Check

23.5

Point

Use Figure 23.3 as an example to show how to apply a bubble sort on {45, 11, 50, 59,
60, 2, 4, 7, 10}.

23.6

If a list is already sorted, how many comparisons will the bubbleSort method
perform?