Bubble Sort in Java

Given an array of n (n>1) numbers, we want to sort them such that the smallest number is on the left, and the largest number is on the right. This is where all the sorting fun comes from. 

Bubble sort is one of the slowest of all sorting algorithms, but it is conceptually the simplest. 

In bubble sort routine, we start by comparing two numbers in the array, say the 1st (array[0]) and 2nd (array[1]) numbers. If the 1st number is larger than the 2nd number, we swap them, otherwise don't do anything. Then we move over one position and compare the 2nd and 3rd numbers, and so on, until we've completed the comparison of the second last and the last number. At this point, the largest number has been bubbled up all the way to the right (array[n-1]). On the 2nd round, we only need to do the comparison and swap from array[0] to array[n-2], which will ensure array[n-2] has the 2nd largest value in the array. Continue like this until the (n-1)th round.

The algorithm complexity, when expressed in Big O notation, is O(N²). This is because, given an array of 10 numbers, you will need 9 comparisons on the first round to bubble the largest number to the right, and 8 comparisons on the second round, and so on, while the last round requires 1 comparison. That is

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45, or n*(n-1)/2, 

where n is the number of elements in the array. On the other hand, a swap is only required when the number on the left is larger than the one on the right, although in the worst case scenario, when the initial array is sorted such that the largest number is on the left and the smallest number is on the right, a swap is necessary for every comparison. Therefore, the number of swaps and comparisons are proportional to n².This is how we work out bubble sort's complexity O(N²).

Below demonstrates one of the implementations of the bubble sort algorithm.

import java.util.Arrays;
import java.util.Random;

public class BubbleSortTest {

    static int numberOfElements = 10;
    static int maxValue = 100;

    public static void main(String[] args) {
        int[] original = createArrayWithRandomValues();

        bubbleSort(original);

        System.out.println("The sorted array is " + Arrays.toString(original));
    }

    private static int[] createArrayWithRandomValues() {
        Random random = new Random();
        int[] original = new int[numberOfElements];
        for (int start = 1; start <= numberOfElements; start++) {
            original[start - 1] = random.nextInt(maxValue);
        }
        System.out.println("The original array is " + Arrays.toString(original));
        return original;
    }

    private static void bubbleSort(int[] original) {
        int outer, inner;
        for (outer = original.length - 1; outer > 1; outer--) { // from last element to the 2nd element
            for (inner = 0; inner < outer; inner++) { // from the 1st element to outer index - 1
                if (original[inner] > original[inner + 1]) { // bubble up the bigger value to the right
                    int temp = original[inner];
                    original[inner] = original[inner + 1];
                    original[inner + 1] = temp;
                }
            }
        }
    }

}