Java Selection Sort with Example

Selection Sort is a simple and slow sorting algorithm that repeatedly selects the lowest or highest element from the un-sorted section and moves it to the end of the sorted section. Mostly, performance wise, it is slower than even Insertion Sort. It does not adapt to the data in any way so its runtime is always quadratic.

But you should not conclude that selection sort should never be used. Good thing is that selection sort has the property of minimizing the number of swaps with each iteration. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

1. Algorithm

Below is the logical code structure or pseudo code of selection sort in general.

for i = 1:n,
k = i
for j = i+1:n, if a[j] < a[k], k = j
//-> invariant: a[k] smallest of a[i..n]
swap a[i,k]
//-> invariant: a[1..i] in final position
end

In plain English, the following things happen:

• Data elements are grouped into two sections: a sorted section (initially empty) and an unsorted section (initially complete array).
• Assuming the sorting order is from low to high, find the element with the lowest comparable order from the un-sorted section.
• Place the found element at the end of the sorted section.
• Repeat steps 2 and 3 until no more elements are left in the un-sorted section.

2. Selection Sort Java Example

Below is a sample selection sort implementation in java.

public class SelectionSortExample 
{
  public static void main(String[] args) {
    // This is unsorted array
    Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };
 
    // Let's sort using selection sort
    selectionSort(array, 0, array.length);
 
    // Verify sorted array
    System.out.println(Arrays.toString(array));
  }
 
  @SuppressWarnings({ "rawtypes", "unchecked" })
  public static void selectionSort(Object[] array, int fromIndex, int toIndex) 
  {
    Object d;
    for (int currentIndex = fromIndex; currentIndex < toIndex; currentIndex++) 
    {
      int indexToMove = currentIndex;
      for (int tempIndexInLoop = currentIndex + 1; tempIndexInLoop < toIndex; tempIndexInLoop++) 
      {
        if (((Comparable) array[indexToMove]).compareTo(array[tempIndexInLoop]) > 0) 
        {
          //Swapping
          indexToMove = tempIndexInLoop;
        }
      }
      d = array[currentIndex];
      array[currentIndex] = array[indexToMove];
      array[indexToMove] = d;
    }
  }
}

If you guys know any way to improve the performance of the selection sort, then please share.

Happy Learning !!