Selection Sort Algorithm using Generics in Java

Today, we are going to show the implementation of the Selection Sort algorithm, which is the third one from our series of tutorials on sorting algorithms. If you haven’t read the first two tutorials on BubbleSort and InsertionSort, I strongly recommend that you go there and read them, because we will reuse code that was explained there.

The application is really simple, it will just get an instance of a Sortable algorithm, which in this case will be an SelectionSort object 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 = newSortable(3);
    sorter.sortAscending(values);
    // sorter.sortDescending(values);
    Utils.printArray(values);
  }

  private Sortable newSortable(int sortableAlgorithm) {
    switch (sortableAlgorithm) {
      case 1:
        return new BubbleSort();
      case 2:
        return new InsertionSort();
      case 3:
        return new SelectionSort();
      default:
        return new BubbleSort();
      }
    }
}

You can see on the code below that the sortAscending and sortDescending invoke the same private method sort 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.

The Sorter Abstract class and the Sortable Interface were explained on the first tutorial of our series.

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

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

Just like Bubble Sort and Insertion Sort, the Selection sort is an in-place comparison sort type of algorithm, which means two things. First, it sorts its elements by doing comparisons between two elements at a time and these elements (input) get sorted inside (in-place) the same structure/object.

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

    int length = values.length;
    int count = 0;
    int indexSwapElement;

    for (int i = 0; i < length - 1; i++) {
      indexSwapElement = i;

      for (int j = i + 1; j < length; j++) {
        count++;

        if (values[indexSwapElement + first].compareTo(values[j - second]) > 0) {
          // It gets the index of the smallest/biggest element.
          indexSwapElement = j;
        }
      }
      if (indexSwapElement != i) {
        // Put the smallest/biggest element at the index i, but only if the values (i and
        // indexSmallestElement) have changed.
        swap(values, i, indexSwapElement);
      }

    }
    System.out.printf("%2s: ", count);
  }
}