Bubble Sort: Implementation and Analysis

Bubble Sort

Bubble Sort is a simple sort algorithm. When sorting a given list of items, in general, Bubble sort will make multiple passes over the list of items. During each pass, Bubble sort compares each adjacent pair of items. If the pair is in the correct order, Bubble sort does nothing and moves to the next adjacent pair. If the pair is out of order, Bubble sort swaps their positions and then moves to the next pair. Once all adjacent pairs have been compared, the pass is complete. Once a pass completes, the last item in the list of considered items is guaranteed to be in its final sorted position. Also, once the pass completes, if any item was swapped, Bubble sort must execute a subsequent pass. Each subsequent pass will consider one less item. This is because the last item considered is guaranteed to be sorted. It has ‘bubbled’ into its sorted position, thus it does not need to be considered in the subsequent pass. Bubble Sort exits once there are no more items left to consider or once a pass completes without performing a swap. If either condition is met, the list of given items is sorted and Bubble sort is done!

The following animation from Commons.WikiMedia helps visualize the algorithm.


The implementation
Below is a Java implementation of the Bubble Sort algorithm.

public static void bubbleSort(char[] chars) {
	boolean sorted = false;
	int pass=1;
	for (; pass < chars.length && !sorted; pass++) {
		// assume sorted
		sorted = true;
		for (int i = 0; i < (chars.length - pass); i++) {
			// iterate over each item in the sequence,
			// excluding items that have 'bubbled' to their proper position.
			// after each pass, the item in the (char.length - pass) position is
			// guaranteed to have 'bubbled' to its correct and final position.
			if (chars[i] < chars[i + 1]) {
				// swap pair if out of order
				char tmp = chars[i];
				chars[i] = chars[i + 1];
				chars[i + 1] = tmp;
				sorted = false;

The Analysis

In general, a pass requires n-1 comparisons and at most n-1 exchanges. Thus we require
(n-1) + (n-2) + ... 1 = n *(n-1)/2 comparisons or O(n^2)
and at most the same exchanges
2n * (n-1) = 2n^2 - 2n or O(n^2)

Bubble sort time complexity:
Worst case: O(n^2) – the same number of comparisons as exchanges
Avg case: O(n^2)– incurs the cost of comparisons, but fewer exchanges.
Best case: O(n) – The list is presorted, therefore 1 pass, and n-1 comparisons, and 0 exchanges are required.

Thank you!

You may also like...


Get every new post on this blog delivered to your Inbox.

Join other followers: