Bubble Sort

A bubble sort sorts the array in multiple phases. Each pass successively swaps the neighboring elements if the elements are not in order. 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 the first pass, the last element becomes the largest in the array. After the second pass, the second-to-last element becomes the second largest in the array. This process is continued until all elements are sorted.

Figure below (a) 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 below.

The first pass places the largest number (9) as the last in the array. In the second pass, as shown in Figure below (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 below (c), you compare and order pairs of elements sequentially except the last two elements, because they are already in order. So in the kth 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 code below.

for (int k = 1; k < list.length; k++) {
// Perform the kth pass
for (int i = 0; i < list.length - k; i++) {
if (list[i] > list[i + 1])
swap list[i] with list[i + 1];
}
}

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 code above as in code below.

boolean needNextPass = true;
for (int k = 1; k < list.length && needNextPass; k++) {
// Array may be sorted and next pass not needed
needNextPass = false;
// Perform the kth pass
for (int i = 0; i < list.length – k; i++) {
if (list[i] > list[i + 1]) {
swap list[i] with list[i + 1];
needNextPass = true; // Next pass still needed
}
}
}

The algorithm can be implemented in code below

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 - 1 passes. The first pass makes n - 1 comparisons; the second pass makes n - 2 comparisons; and so on; the last pass makes 1 comparison. Thus, the total number of comparisons is:

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

The above is the detailed content of Bubble Sort. For more information, please follow other related articles on the PHP Chinese website!