BubbleSort.java

package Sorting;

import java.util.Random;

public class BubbleSort {

  // Sort the array using bubble sort. The idea behind
  // bubble sort is to look for adjacent indexes which
  // are out of place and interchange their elements
  // until the entire array is sorted.
  public static void bubbleSort(final int[] ar) {
        if (ar == null)
            return;

        final int N = ar.length;
        boolean sorted;

        do {

            sorted = true;

            for (int i = 1; i < N; i++) {
                if (ar[i] < ar[i - 1]) {
                    swap(ar, i - 1, i);
                    sorted = false;
                }
            }

        } while (!sorted);
    }

    private static void swap(final int[] ar, final int i, final int j) {
        final int tmp = ar[i];
        ar[i] = ar[j];
        ar[j] = tmp;
    }

    public static void main(final String[] args) {

        final int[] array = { 10, 4, 6, 8, 13, 2, 3 };
        bubbleSort(array);
        System.out.println(java.util.Arrays.toString(array));

        // TODO(williamfiset): move to javatests/...
        runTests();
    }

    static Random RANDOM = new Random();

    public static void runTests() {
        final int NUM_TESTS = 1000;
        for (int i = 1; i <= NUM_TESTS; i++) {

            final int[] array = new int[i];
            for (int j = 0; j < i; j++)
                array[j] = randInt(-1000000, +1000000);
            final int[] arrayCopy = array.clone();

            bubbleSort(array);
            java.util.Arrays.sort(arrayCopy);

            if (!java.util.Arrays.equals(array, arrayCopy))
                System.out.println("ERROR");
        }
    }

    static int randInt(final int min, final int max) {
    return RANDOM.nextInt((max - min) + 1) + min;
  }
}