The Bubble Sort algorithm gets it’s name from the fact that on each pass, one element of the array ‘bubbles’ it’s way through to it’s correct (sorted) position in the array. Rather than me try and explain the details the following video gives a great visual demonstration of how the algorithm works. The source code is also heavily commented to explain how the bubble sort is implemented.

If you Google “Java Bubble Sort” you will be presented with a multitude of examples which use two loops to implement the bubble sort. Although these examples all correctly sort the array, the majority of them scan the entire array on each pass which is unnecessary. Remember that after each pass another element in the array is in the correct position, so each pass has less to check.

Additionally if on any given pass we don’t swap any elements then we know that the array is correctly sorted and we

package com.learnjava.math.sort; import java.util.Random; /** * Write a program to sort an array of numbers using a Bubble Sort * * @author http://learn-java-by-example.com * */ public class BubbleSort { public static void main(String[] args) { // Create an array of random numbers to sort int[] data = generateData(); // Display the unsorted data System.out.println("Unsorted data:"); printArray(data); // Sort the array bubbleSort(data); // Display the sorted data System.out.println("Sorted data:"); printArray(data); } private static void bubbleSort(int[] data) { int n = data.length; // Assume the array initially unsorted boolean sorted = false; // Keep track of which pass we are on // // A pass involves one trip through // the array comparing and swapping elements // // After each pass (at least) one extra // element will be in the correct position int pass = 1; // We loop until the array is sorted // We know the array is sorted if we // do a complete pass without swapping any elements while (!sorted) { // Initially assume it is sorted // We'll toggle this flag if a swap is needed sorted = true; // Perform a pass // After each pass we know another // element in the array is correctly sorted // So we don't need to loop through the entire array for (int j=0; j<n-pass; j++) { // Check if the value needs to be swapped or not if (data[j] > data[j+1]) { // Swap values int temp = data[j]; data[j] = data[j+1]; data[j+1] = temp; // Array may not be sorted, // so need another pass sorted = false; } } // Print out the array after we have // finished each element to see the progress System.out.println("Pass " + pass); printArray(data); pass++; } } private static int[] generateData() { Random random = new Random(); int[] data = new int[10]; for (int i=0; i<data.length; i++) { data[i] = random.nextInt(100); } return data; } private static void printArray(int[] data) { for (int i=0; i<data.length; i++) { System.out.print(data[i]); System.out.print(", "); } System.out.println(); } }