Bubble Sort is the simplest algorithm for sorting a set of data, and also the slowest. The procedure goes like this:
- Find the largest item and place it at the end of the items that were searched.
- Remove the largest item most recently found from the set to be searched and go to step a.
- (Repeat parts a. and b. until the number of items to be searched is zero.)
The Bubble Sort algorithm uses the simplest method for determining the largest item in a list: it compares two items at a time and then moves on to compare the larger of the two with the next item in the list. After each comparison, the larger item must be identified and "swapped" into position to be compared with the next item.
The following program implements the Bubble Sort algorithm.
public static void bubbleSort(int[] list)
{
for (int outer = 0; outer < list.length - 1; outer++)
{
for (int inner = 0; inner < list.length-outer-1; inner++)
{
if (list[inner] > list[inner + 1])
{
//swap list[inner] & list[inner+1]
int temp = list[inner];
list[inner] = list[inner + 1];
list[inner + 1] = temp;
}
}
}
}
-
Given an array of 6 values, the loop variables outer
and inner
will evaluate as follows:
| When outer = | inner ranges from |
| | 0 to < (6 - outer - 1) |
| | |
| 0 | 0 to 4 |
| 1 | 0 to 3 |
| 2 | 0 to 2 |
| 3 | 0 to 1 |
| 4 | 0 to 0 |
-
When outer = 0
, then the inner loop will do 5 comparisons of values next to each other. As inner
ranges from 0–4, it does the following comparisons:
| inner | if list[inner] > list[inner + 1] |
| | |
| 0 | if list[0] > list[1] |
| 1 | if list[1] > list[2] |
| ... | ... |
| 4 | if list[4] > list[5] |
If (list[inner] > list[inner+1]
) is true
, then the values are out of order and a swap takes place. The swap takes three lines of code and uses a temporary variable temp
.
After the first pass (outer = 0
), the largest value will be in its final resting place. When outer = 1
, the inner
loop only goes from 0 to 3 because a comparison between positions 4 and 5 is unnecessary. The inner
loop is shrinking.
Because of the presence of duplicate values this algorithm will result in a list sorted in nondecreasing order.
Here is a small list of data to test your understanding of Bubble Sort. Write in the correct sequence of integers after each advance of outer
.
| outer | 57 | 95 | 88 | 14 | 25 | 6 |
| | | | | | | |
| 0 |
|
|
|
|
|
|
| 1 |
|
|
|
|
|
|
| 2 |
|
|
|
|
|
|
| 3 |
|
|
|
|
|
|
| 4 |
|
|
|
|
|
|