Bubble Sort
Bubble Sort is the simplest of the three sorting algorithms, and also the slowest. The Bubble Sort gets its name from
the way that the largest items “bubble” to the top (end). The procedure goes like this.
Move the largest remaining item in the current pass to the end of the data as follows. Starting with the first two
items, swap them if necessary so that the larger item is after the smaller item. Now move over one position in the
list and compare to the next item. Again swap the items if necessary.
Remove the largest item most recently found from the data to be searched and perform another pass with this new data
at step 1.
Repeat steps 1 and 2 above until the number of items to be searched is one.
To see how Bubble Sort works, let’s try an example:
| Steps |
Data for Pass |
Sorted data |
| Start pass 1: compare 4 & 1 |
4 1 3 2 |
|
| 4 > 1 so swapped, now compare 4 & 3 |
1 4 3 2 |
|
| 4 > 3 so swapped, now compare 4 & 2 |
1 3 4 2 |
|
| 4 > 2 so swapped, end of pass |
1 3 2 4 |
|
| Start pass 2: compare 1 & 3 |
1 3 2 |
4 |
| 3 > 1 so no swap, now compare 3 & 2 |
1 3 2 |
4 |
| 3 > 2 so swapped, end of pass |
1 2 3 |
4 |
| Start pass 3: now compare 1 & 2 |
1 2 |
3 4 |
| 2 > 1 so no swap |
1 2 |
3 4 |
| Only one item in this pass so it is done |
1 |
2 3 4 |
| Done. |
|
1 2 3 4 |
The following program implements the Bubble Sort algorithm.
void bubbleSort(ArrayList <Integer> list){
for (int outer = 0; outer < list.size() - 1; outer++){
for (int inner = 0; inner < list.size()-outer-1; inner++){
if (list.get(inner) > list.get(inner + 1)){
//swap list[inner] & list[inner+1]
int temp = list.get(inner);
list.set(inner, list.get(inner + 1));
list.set(inner + 1, temp);
}
}
}
}
Given a list 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 pairs of values. As inner ranges from 0 to 4, it does the following comparisons:
| inner |
if (list.get(inner) > list.get(inner + 1)) |
| 0 |
if list[0] > list[1] |
| 1 |
if list[1] > list[2] |
| ... |
... |
| 4 |
if list[4] > list[5] |
If (list.get(inner) > list.get(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 (and may it rest in peace). 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 non-decreasing order.
Tino APCS