Bubble Sort

Overview

Also known as sinking sort, Bubble Sort is a simple sorting algorithm which repeatedly steps through the array (or list) to be sorted and compares each pair of adjacent items and swaps them if they are not in the correct order.

Concept

The concept of Bubble Sort is pretty easy to understand. It simply iterates over the list, swapping the values of any two adjacent values as necessary and repeats the process until the list no longer needs any swaps.

Algorithmic Complexity

Big-0

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
Bubble SortArrayO(n)O(n^2)O(n^2)O(1)

 

Implementation

Java Implementation


import java.util.Arrays;

/**
 * Bubble Sort algorithm implementation
 * 
 * www.algorithmiccomplexity.com
 */
public class BubbleSort {
	
	public static int[] bubbleSort(int[] unsortedArray)
	{
		boolean swapped;
		
		do
		{
			swapped = false;
			for(int i = 0; i < unsortedArray.length - 1; i++)
			{
				if(unsortedArray[i+1] < unsortedArray[i])
				{
					int temp = unsortedArray[i+1];
					unsortedArray[i+1] = unsortedArray[i];
					unsortedArray[i] = temp;
					swapped = true;
				}
			}
		} while(swapped);
		
		return unsortedArray;
	}
	
	/**
	 * Test driver for the bubble sort algorithm.
	 * 
	 * @param args Command line arguments {@code null}.
	 */
	public static void main(String[] args)
	{
		int[] unsortedArray = new int[9];
		unsortedArray[0] = 10;
		unsortedArray[1] = 5;
		unsortedArray[2] = 3;
		unsortedArray[3] = 7;
		unsortedArray[4] = 1;
		unsortedArray[5] = 8;
		unsortedArray[6] = 8;
		unsortedArray[7] = 0;
		unsortedArray[8] = 6;
		
		System.out.println(Arrays.toString(unsortedArray));
		unsortedArray = BubbleSort.bubbleSort(unsortedArray);
		System.out.println(Arrays.toString(unsortedArray));
	}
}

References

Wikipedia: Bubble sort

 

<- back