Visual Basic
Web Scripting
Active Server Page


Home


Articles

Links
Books

Mailing List
Receive free code snippets and notices when this site is updated.

Email

Feedback

 

Sorting Algorithms in Java

  Time Growth Rate
Best Case
Time Growth Rate
Average Case
Time Growth Rate
Worst Case
Bubble Sort N  N2 N2

Bubble Sort

Like the selection sort this implementation of a bubble sort takes up to N2 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 N-1 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.