Bubble sort is a simple algorithm that basically bubbles up the elements of the array. This means that it traverses the array multiple times and swaps the adjacent elements if they are in the wrong order, as in the following diagram:

The time complexity cases are as follows: best case O(n), average case O(n²), and worst case O(n²)

The space complexity case is as follows: worst case O(1)

A utility method implementing the Bubble sort is as follows:

public static void bubbleSort(int[] arr) {

  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {

      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

There is also an optimized version of it that relies on a while loop. You can find it in the code bundled to this book under the name bubbleSortOptimized().

As a performance comparison of time execution, for a random array of 100,000 integers, the optimized version will work around 2 seconds faster.

The preceding implementations work well for sorting arrays of primitives, but, for sorting an array of Object, we need to bring Comparator into the code, as follows:

public static <T> void bubbleSortWithComparator(
    T arr[], Comparator<? super T> c) {

  int n = arr.length;

  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {

      if (c.compare(arr[j], arr[j + 1]) > 0) {
        T temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

Remember the Melon class from before? Well, we can write a Comparator for it by implementing the Comparator interface:

public class MelonComparator implements Comparator<Melon> {

  @Override
  public int compare(Melon o1, Melon o2) {
    return o1.getType().compareTo(o2.getType());
  }
}

Or, in Java 8 functional style, we have the following:

// Ascending
Comparator<Melon> byType = Comparator.comparing(Melon::getType);

// Descending
Comparator<Melon> byType 
  = Comparator.comparing(Melon::getType).reversed();

Having an array of Melon, the preceding Comparator, and the bubbleSortWithComparator() method in a utility class named ArraySorts, we can write something along the lines of the following:

Melon[] melons = {...};
ArraySorts.bubbleSortWithComparator(melons, byType);

For brevity, the Bubble sort optimized version with a Comparator was skipped, but it is available in the code bundled to the book.