Selection Sort with Java

The Selection sort is not the most performant but it’s an easy one to implement. Simply put, the selection sort will have two subarrays. The sorted part in the left, and the unsorted part is on the right.

The selection sort will select the smallest element of the array by comparing each number and changing the smallest element index whenever it finds a smaller element.

Once it finds the smallest index of the array it will swap this element to the left-most part of the array (left subarray) and will continue until the array is fully sorted.

Let’s see what is the idea with the following diagram:

import java.util.Arrays;

public class SelectionSort {

  public static void main(String[] args) {
    int[] array = {5, 2, 3, 7, 1};
    var sortedArray = sort(array);
    System.out.println(Arrays.toString(sortedArray));
  }

  static int[] sort(int[] array) {
    if (array.length == 1) {
      return array;
    }

    var firstUnsortedIndex = 0;

    while (firstUnsortedIndex < array.length - 1) {
      var smallestElementIndex = firstUnsortedIndex;
      for (int i = firstUnsortedIndex; i < array.length; i++) {
        if (i != smallestElementIndex && array[i] < array[smallestElementIndex]) {
          smallestElementIndex = i;
        }
      }

      swapElements(array, firstUnsortedIndex, smallestElementIndex);
      firstUnsortedIndex++;
    }

    return array;
  }

  private static void swapElements(int[] array, int i, int j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

}

Output:
[1, 2, 3, 5, 7]

Code analysis:

• Initialize variables firstUnsortedIndex and smallestElementIndex with 0.
• while looping to iterate over the whole array.
• Set the firstUnsortedIndex to the smallestElementIndex to avoid comparisons with already sorted elements.
• Iterate the array again to find the smallestElementIndex.
• When the whole array is iterated, swap the smallest element to the left subarray.
• Increase the firstUnsortedIndex to do the operation again until the end of the array.

Selection Sort By Comparing Element Lowest Value

public class SelectionSort {
  // Omitted above code

  public static int[] sortMaxValue(int[] array) {
    var smallestElementIndex = 0;

    for (int i = 0; i < array.length; i++) {
      var smallestElement = Integer.MAX_VALUE;
      for (int j = i; j < array.length; j++) {
        if (array[j] < smallestElement) {
          smallestElement = array[j];
          smallestElementIndex = j;
        }
      }

      swapElements(array, i, smallestElementIndex);
      smallestElementIndex = 0;
    }
    return array;
  }

  // Omitted swapElements method
}

Code analysis:

The code above will do the same as the first code example but the difference is that instead of comparing the elements from the array directly, we are setting the smallest number to a variable smallestElement. It’s a different code technique to solve the same problem.

Big (O) Notation Complexity

Time Complexity: Since the iteration happens first for the “sorted subarray” and then goes through the “unsorted subarray” the complexity will be O(n^2). Keep in mind that this is not a precise number and it’s the worst-case scenario for this algorithm.

Space Complexity: Since we only swap some numbers in the array in place, the space complexity for this algorithm is O(1).

Summary

The selection sort is not very performant but it’s easy enough to implement. Let’s see the main points of this algorithm:

• The left part of the array will be sorted and the right part will be unsorted.
• The smallest element index will be selected. Once it’s selected the array values are swapped.
• It’s possible to sort elements by comparing the array elements or comparing the smallest number from another variable.