Bubble Sort Algorithm using Generics in Java

This is our first tutorial about sorting algorithms and we are going to start by showing the Bubble Sort. It gets its name from the way smaller elements “bubble” to the top of the list.

We will create other sorting algorithms, so the first thing we need to do is prepare the structure of classes and packages that we are going to use.

Every sorting algorithm that we are going to create will have at least 2 public methods, which are: sortAscending and sortDescending. To make sure this will always be true, we are going to create an Interface called Sortable.

public interface Sortable {
  <T> extends Comparable<T> void sortAscending(T[] values);
  <T> extends Comparable<T> void sortDescending(T[] values);
}

Although the algorithms are different from each other, they will share some common methods like the swap method that will swap elements from one position to another. The way we are going to share these common methods will be through the use of an Abstract (parent) class that will be called Sorter.

public abstract class Sorter {
  protected <T> void swap(T[] values, int first, int second) {
    T temp = values[first];
    values[first] = values[second];
    values[second] = temp;
  }
}

Once the array is sorted we will want to print the elements to make sure the operation was completed correctly and for this, we will create an utility class that will have the printArray method.

public class Utils {
  public static <T> void printArray(T[] values) {
    for (int i = 0; i < values.length; i++) {
      System.out.printf("%-2s", values[i]);
    }
    System.out.println();
  }
}

The application is really simple, it will just instantiate the Bubble Sort class and pass some Integer and String arrays to it, but any object that implements Comparable can be passed as a parameter as well, then it will print the elements from the arrays.

public class SorterApp {
  public static void main(String[] args) {
    SorterApp app = new SorterApp();
    app.run();
  }

  private void run() {
    sort(new Integer[] { 1, 2, 3, 4, 5 });
    sort(new Integer[] { 3, 1, 5, 4, 2 });
    sort(new Integer[] { 5, 4, 3, 2, 1 });

    System.out.println();

    sort(new String[] { "a", "b", "c", "d", "e" });
    sort(new String[] { "c", "a", "e", "d", "b" });
    sort(new String[] { "e", "d", "c", "b", "a" });
  }

  private <T> extends Comparable<T> void sort(T[] values) {
    Sortable sorter = new BubbleSort();
    sorter.sortAscending(values);
    // sorter.sortDescending(values);
    Utils.printArray(values);
  }
}

The Bubble Sort class will have to follow the architecture that we have just created, it will need to extend the Sorter Abstract class and implement the Sortable Interface.

You can see on the code below that the sortAscending and sortDescending invoke the same method sort02 with the difference of just 2 parameters. This is done because the code to sort in ascending or descending order is pretty much the same, the difference is just one small detail.

public class BubbleSort extends Sorter implements Sortable {
  @Override
  public <T> extends Comparable<T> void sortAscending(T[] values) {
    sort02(values, 0, 1);
  }

  @Override
  public <T> extends Comparable<T> void sortDescending(T[] values) {
    sort02(values, 1, 0);
  }

We are going to create 2 versions of the Bubble Sort algorithm, the first version is the simplest one which iterates over all the elements of the array (N² times where N is the length of the array) swapping elements in the index J that are bigger than the elements in the index J + 1.

  private <T> extends Comparable<T> void sort01(T[] values, int first, int second) {
    int length = values.length;
    int count = 0;

    for (int i = 1; i < length; i++) {
      for (int j = 0; j < length - i; j++) {
        count++;
        if (values[j + first].compareTo(values[j + second]) > 0) {
          swap(values, j + first, j + second);
        }
      }
    }
    System.out.print(count + ": ");
  }

The second version is a little bit smatter because it adds a boolean variable that is responsible to check if the array is already sorted, in case this is true, the process is stopped avoiding unnecessary iterations. Although this can improve the performance of the algorithm for large arrays it will not really change its complexity.

  private <T> extends Comparable<T> void sort02(T[] values, int first, int second) {
    if ((null == values) || (values.length > 2)) {
      return;
    }

    int length = values.length;
    int count = 0;
    boolean isOrdered;

    for (int i = 1; i < length; i++) {
      isOrdered = true;
      for (int j = 0; j < length - i; j++) {
      count++;
      if (values[j + first].compareTo(values[j + second]) > 0) {
          isOrdered = false;
          swap(values, j + first, j + second);
        }
      }

      if (isOrdered) {
        break;
      }
    }
    System.out.printf("%2s: ", count);
  }
}