Java Reference
In-Depth Information
I=0
1
2
3
4
5
6
42
20
17
13
28
14
23
13
42
20
17
14
28
15
13
14
42
20
17
15
28
23
13
14
15
42
20
17
23
28
13
14
15
17
42
20
23
28
13
14
15
17
20
42
23
28
13
14
15
17
20
23
42
13
14
15
17
20
23
28
42
15
23
28
Figure7.2
An illustration of Bubble Sort. Each column shows the array after
the iteration with the indicated value of
i
in the outer
for
loop. Values above the
line in each column have been sorted. Arrows indicate the swaps that take place
during a given iteration.
neighbor, then the two values are swapped. Once the smallest value is encountered,
this process will cause it to “bubble” up to the top of the array. The second pass
through the array repeats this process. However, because we know that the smallest
value reached the top of the array on the first pass, there is no need to compare
the top two elements on the second pass. Likewise, each succeeding pass through
the array compares adjacent elements, looking at one less value than the preceding
pass. Figure 7.2 illustrates Bubble Sort. A Java implementation is as follows:
static<EextendsComparable<?superE>>
voidSort(E[]A){
for(inti=0;i<A.length-1;i++)//Bubbleupi'threcord
for(intj=A.length-1;j>i;j--)
if((A[j].compareTo(A[j-1])<0))
DSutil.swap(A,j,j-1);
}
Determining Bubble Sort's number of comparisons is easy. Regardless of the
arrangement of the values in the array, the number of comparisons made by the
inner
for
loop is always i, leading to a total cost of
n
X
i n
2
=2 = (n
2
):
i=1
Bubble Sort's running time is roughly the same in the best, average, and worst
cases.
The number of swaps required depends on how often a value is less than the
one immediately preceding it in the array. We can expect this to occur for about
half the comparisons in the average case, leading to (n
2
) for the expected number
of swaps. The actual number of swaps performed by Bubble Sort will be identical
to that performed by Insertion Sort.
