Bubble Sort Java Example

Bubble Sort is a simple and slow sorting algorithm that repeatedly steps through the collection, compares each pair of adjacent elements and swaps them if they are in the wrong order. In the sorting algorithm, if you watch the move of the elements with higher orders (i.e. larger values), they are like bubbles in the water, floating slowly from the bottom to the top (from one side/middle of wrray to other side of array).

You can imagine that on every step big bubbles float to the surface and stay there. At the step, when no bubble moves, sorting stops.

Bubble Sort Algorithm

The basic idea of Bubble Sort algorithm can be described as these steps:

1. Data elements are grouped into two sections: a sorted section and an un-sorted section.
2. Go through every element in the un-sorted section and re-arrange its position with its neighbor to put the element with higher order on the higher position. At the end, the element with the highest order will be on top of the un-sorted section, and moved to the bottom of the sorted section.
3. Repeat step 2 until no more elements left in the un-sorted section.

Bubble Sort Java Example

public class BubbleSortExample 
{
	public static void main(String[] args) 
	{
		// This is unsorted array
		Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };

		// Let's sort using bubble sort
		bubbleSort(array, 0, array.length);

		// Verify sorted array
		System.out.println(Arrays.toString(array));
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void bubbleSort(Object[] array, int fromIndex, int toIndex) 
	{
		Object d;
		for (int i = toIndex - 1; i > fromIndex; i--) 
		{
			boolean isSorted = true;
			for (int j = fromIndex; j < i; j++) 
			{
				//If elements in wrong order then swap them
				if (((Comparable) array[j]).compareTo(array[j + 1]) > 0) 
				{
					isSorted = false;
					d = array[j + 1];
					array[j + 1] = array[j];
					array[j] = d;
				}
			}
			//If no swapping then array is already sorted
			if (isSorted)
				break;
		}
	}
}

Output: [3, 6, 10, 12, 13, 24, 70, 90]

Bubble Sort Performance and Complexity

1. Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes.
2. Bubble sort is both stable and adaptive.
3. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data.
4. It can be practical if the input is usually in sort order but may occasionally have some out-of-order elements nearly in position.
5. Bubble sort should be avoided in the case of large collections.
6. It will not be efficient in the case of a reverse-ordered collection.

Happy Learning !!