## 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 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;
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();
}
}

```