| | |
In the bubble sort, one repeatedly traverses the array in question, swapping adjacent entries when they are not in order (e.g., ascending order) relative to one another. So for example, if we wished to sort the array 5, 1, 2, 9, 3, 7 using a bubble sort, we would see the following swaps in the first pass:
=== First Pass ==============================
5 2 4 1 9 3 7 (swap, as 5 > 2)
- -
2 5 4 1 9 3 7 (swap, as 5 > 4)
- -
2 4 5 1 9 3 7 (swap, as 5 > 1)
- -
2 4 1 5 9 3 7 (don't swap, as 5 < 9)
- -
2 4 1 5 9 3 7 (swap, as 9 > 3)
- -
2 4 1 5 3 9 7 (swap, as 9 > 7)
- -
2 4 1 5 3 7 9 <-- end of first pass
We can see that when we start swapping, the largest element is carried as far to the right as it can go before hitting something even larger.
Since the maximum value in the list is bigger than everything else, we can be assured that after the first pass through the array, the maximum element will have moved all the way to the end. As such, there is no need for the second pass through the array to consider swapping anything with the last element -- which shortens the number of comparisons we need to make by one.
In a like manner and presuming the array is of size n, the third pass will only have to consider comparisons between consecutive elements of the array up to but not including the last two elements. Similarly, the fourth pass will only have to consider comparisons up to, but not including the last three elements, and so on...
So the maximum number of passes we will need to make for an array of size $n$ is $n-1$. (Note, if the last $n-1$ elements have been put in the correct position, then the first element must also be in the correct position.) Of course, if a given pass never produced any swaps -- then we know the array is in order already, and we can stop.
Below the rest of the passes are shown for the array considered above...
==== Second Pass ============================
2 4 1 5 3 7 9 (don't swap, as 2 < 4)
- -
2 4 1 5 3 7 9 (swap, as 4 > 1)
- -
2 1 4 5 3 7 9 (don't swap, as 4 < 5)
- -
2 1 4 5 3 7 9 (swap, as 5 > 3)
- -
2 1 4 3 5 7 9 (don't swap, as 5 < 7)
- -
2 1 4 3 5 7 9 <-- end of second pass
Note: we don't compare 7 and 9,
as we know the last element (9)
must already be in the correct
position
==== Third Pass ============================
2 1 4 3 5 7 9 (swap, as 2 > 1)
- -
1 2 4 3 5 7 9 (don't swap, as 2 < 4)
- -
1 2 4 3 5 7 9 (swap, as 4 > 3)
- -
1 2 3 4 5 7 9 (don't swap as 4 < 5)
- -
1 2 3 4 5 7 9 <-- end of second pass
Note: we don't compare 5 and 7,
as we know the second-to-last
element (7) must already be in
the correct position
=== Fourth Pass ============================
1 2 3 4 5 7 9 (don't swap, as 1 < 2)
- -
1 2 3 4 5 7 9 (don't swap, as 2 < 3)
- -
1 2 3 4 5 7 9 (don't swap, as 3 < 4)
- -
1 2 3 4 5 7 9 <-- end of third pass
Note: we don't compare 4 and 4,
as we know the third-to-last
element (5) must already be in
the correct position
==================================
As no swaps were made in the previous pass,
the array must now be sorted. So we stop.
Implementing the bubble sort algorithm is fairly straight-forward, using the helper methods less() and exch() mentioned previously, as seen below
public static void bubbleSort(Comparable[] a) {
boolean sorted = false;
int tail = a.length - 1;
while (! sorted) {
sorted = true;
for (int i = 0; i < tail; i++) {
if (less(a[i+1], a[i])) {
exch(a,i,i+1);
sorted = false;
}
}
tail--;
}
}
If we focus on the cost of the method above in terms of number of comparisons, in the worst case (i.e., when our list is in reverse-order), we will have to make $n-1$ comparisons in the first pass, $n-2$ comparisons in the second pass, $n-3$ in the third, and so on -- until we make 1 comparison in the final pass. But then the total number of comparisons is given by:
$$(n-1) + (n-2) + (n-3) + \cdots + 3 + 2 + 1 = \frac{n(n-1)}{2} = O(n^2)$$
If we focus on the cost of the method above in terms of number of exchanges (i.e., swaps), then again in the worst case, when the list is in reverse-order, we must make an exchange for every comparison made. So here again, the cost is $\frac{n(n-1)}{2}$, which is $O(n^2)$. In the best case, the list would be in order already, in which case no exchanges are made. In the average case, we end up splitting the difference with a cost of $\frac{n(n-1)}{4}$, but this is still $O(n^2)$.
Consequently, regardless of whether we are talking about comparisons or exchanges, the bubble sort takes an inordinate amount of time to execute for large $n$. We can do better...