The Bubble Sort Algorithm

BubbleSort is a very simple sorting algorithm which is great for introducing the basics of sorting. While it is extremely simple to code, its running time leaves much to be desired. As its name implies, the bubble sort algorithm works by having the largest element in the list (bubble) slowly move to the end and the smallest element slowly move to the beginning of the array. This is done by comparing every adjacent pair of values and swapping them if the first one is greater than the second. Each pass through the list keeps track of whether a swap has been made. The process runs through the list repeatedly until no swaps are made and then loop terminates.

One possible way to code the BubbleSort algorithm in Java is as follows:

public int[] bubbleSort(int array[])
// pre: array is full, all elements are valid integers (not null)
// post: array is sorted in ascending order (lowest to highest)
{
	boolean swappedOnPrevRun = true;
	while(swappedOnPrevRun)
	{
		swappedOnPrevRun = false;			// this variable keeps track of whether to continue sorting or exit
		for(int i = 0; i < array.length - 1; i++)	// loop through every element in the array,
								// except for the last one
		{
			if(array[i] > array[i + 1])		// if current element is greater than the next
			{
				// swap the two elements
				swappedOnPrevRun = true;	// we don't want the loop to end just yet, we're not done
				int temp = array[i];		// store element i in a temporary variable
				array[i] = array[i + 1];	// set element i+1 to where i used to be
				array[i + 1] = temp;		// release the old i from temp into i+1 slot
			}
		}
	}
	return array;
}

These are the steps taken to sort an array using BubbleSort:

Elements in blue indicate comparisons.
Elements in red indicate swaps.
The green dash indicates return to position 0.

[3][5][4][9][2] -- original
-
[3][5][4][9][2] -- compare 3 to 5
[3][5][4][9][2] -- compare 5 to 4
[3][4][5][9][2] -- swap 4 and 5
[3][4][5][9][2] -- compare 5 to 9
[3][4][5][9][2] -- compare 9 to 2
[3][4][5][2][9] -- swap 2 and 9
-
[3][4][5][2][9] -- compare 3 to 4
[3][4][5][2][9] -- compare 4 to 5
[3][4][5][2][9] -- compare 5 to 2
[3][4][2][5][9] -- swap 2 and 5
[3][4][2][5][9] -- compare 5 to 9
-
[3][4][2][5][9] -- compare 3 to 4
[3][4][2][5][9] -- compare 4 to 2
[3][2][4][5][9] -- swap 2 and 4
[3][2][4][5][9] -- compare 4 to 5
[3][2][4][5][9] -- compare 5 to 9
-
[3][2][4][5][9] -- compare 3 to 2
[2][3][4][5][9] -- swap 2 and 3
[2][3][4][5][9] -- compare 3 to 4
[2][3][4][5][9] -- compare 4 to 5
[2][3][4][5][9] -- compare 5 to 9
-
[2][3][4][5][9] -- compare 2 to 3
[2][3][4][5][9] -- compare 3 to 4
[2][3][4][5][9] -- compare 4 to 5
[2][3][4][5][9] -- compare 5 to 9
[2][3][4][5][9] -- no changes (swaps) were made in the last run, so we are done!

Written by Pavel. Thanks to Eugene Jitomirsky for certain ideas.

Copyright © 2005-2016 MyCSTutorials.com