Bubble Sort

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 https://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();
	}
}

Leave a Reply

s2Member®