
Time Growth Rate
Best Case 
Time Growth Rate
Average Case 
Time Growth Rate
Worst Case 
Bubble Sort 
N 
N^{2} 
N^{2} 
Bubble Sort
Like the selection sort this implementation of a bubble sort takes up
to N^{2} operations to sort a list in the worst case.
A bubble sort can be a good choice if the data is likely to already
be sorted because if it is the bubble sort would require only N1
comparisons and no exchanges.
The bubble sort compares adjacent items
and swaps them if they are out of order.
The bubble sort starts by comparing the first and second items
in a list. They are swapped if the first item is larger then
the second item. Then the second and third items are
compared and swapped if necessary and so on.
The largest items bubble to the right. After each
pass one more item will be in it's correct position at the end of
the array.
Passes are made over the array until there has been no swaps
made.
The figure to the right illustrates this.
The largest item found in each search is in blue.
The item it is swapped with is in green
. The items that have already been sorted are Bold. 
Pass One (4 Comparisons)
25 
9 
13 
47 
12 
Compare 
9 
25 
13 
47 
12 
Swap 
9 
25 
13 
47 
12 
Compare 
9 
13 
25 
47 
12 
Swap 
9 
13 
25 
47 
12 
Compare (No Swap) 
9 
13 
25 
47 
12 
Compare 
9 
13 
25 
12 
47 
Swap 
Pass Two (3 Comparisons)
9 
13 
25 
12 
47 
Compare (No Swap) 
9 
13 
25 
12 
47 
Compare (No Swap) 
9 
13 
25 
12 
47 
Compare 
9 
13 
12 
25 
47 
Swap 
Pass Three (2 Comparisons)
9 
13 
12 
25 
47 
Compare (No Swap) 
9 
13 
12 
25 
47 
Compare 
9 
12 
13 
25 
47 
Swap 
Pass Four (1 Comparisons)
9 
13 
12 
25 
47 
Compare (No Swap) 

Below is an implementation of the Bubble Sort algorithm. L
specifies were in the array to start sorting and R specifies what
element to stop sorting at.
Each time the outer loop executes one more item will be in it's
correct position at the end of the array.
The bubble sort will terminate as soon as there has been no exchanges
made in the inner loop.
public static void bubbleSort(double arrayToSort[], int L, int R)
{
int I=0;
boolean sorted = false;
double temp;
for ( ; (R > L) && !sorted; R) {
sorted = true; // assume that array is sorted
for (I = L; I < R; I++)
if ( arrayToSort[I] > arrayToSort[I + 1] )
{
temp = arrayToSort[I];
arrayToSort[I] = arrayToSort[I + 1];
arrayToSort[I + 1] = temp;
sorted = false; // there was a swap so array may not be sorted.
}
}
}

Next week I will present an implementation of a Insertion Sort.