Selection Sort Implementation in Java

• Implement Selection Sort Algorithm in Java
• Java Program Code for Selection Sort
• Pros and Cons of Selection Sort
• Analysis of Selection Sort
• References

Implement Selection Sort Algorithm in Java

Before implementing Java program for selection sort let's first see how selection sort functions to sort array elements in either ascending or descending order. Selection sort improves a little on the bubble sort by reducing the number of swaps necessary from O(N²) to O(N). However, the number of comparisons remains O(N²). The selection sort can offer a significant improvement for large records that must be physically moved around in memory, causing the swap time to be much more important than the comparison time. (Typically, this isn't the case in Java, where references are moved around, and not entire objects.)

Java Program Code for Selection Sort

Developing Java code for selection sort is quite easy. The idea upon selection sort works is simple; a selection sort selects the element with the lowest value and exchanges it with the first element. Then, from the remaining N-1 elements, the element with the smallest key is found and exchanged with the second element, and so forth. The exchanges continue till the last two elements. Following program develops a class SelectionSort containing a static generic method selectionSort. Note that Java provides the java.util.Comparable interface that contains a single method, compareTo. Any class that correctly implements this interface guarantees a total ordering of its instances.

class SelectionSort 
{
  public static <T extends Comparable<T>> void selectionSort (T[] list, int size) 
  {
    int outCounter, inCounter, minIndex; 
    T temp;
    // swapOccurred helps to stop iterating if the array gets sorted before 
    // outCounter reaches to size
    for (outCounter = 0; outCounter < size - 1; outCounter++)
    {
      minIndex = outCounter;
      for (inCounter = outCounter + 1; inCounter < size; inCounter++)
      {
        if (list[minIndex].compareTo(list[inCounter]) > 0)
          minIndex = inCounter;
      }
 
      //swap items
      if (minIndex != outCounter)
      {
        temp = list[minIndex];
        list[minIndex] = list[outCounter];
        list[outCounter] = temp;
      }
    }
  }
}
 
public class SelectionSortDemo
{
  public static void main (String[] args)
  {
    Integer arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    SelectionSort.selectionSort(arr, arr.length);
 
    System.out.println("Sorted Array: ");
    for(Integer i : arr)
      System.out.println(i);
  }
}
OUTPUT
======
Sorted Array:
1
2
3
4
5
6
7
8
9
10

In above implementation we test a condition minIndex != outCounter before swapping elements just to save unessential swaps. If minIndex remains equal to outCounter, then the element pointed by minIndex is the smallest and no swap is required.

Pros and Cons of Selection Sort

Simplicity is the main benefit of using selection sort. It is an algorithm that is easy to understand and implement. On the downside, selection sort is very inefficient at sorting lists containing large quantities of data. It has an algorithmic complexity of O(N²).

Analysis of Selection Sort

For large values of N, the comparison times dominate, so we would have to say that the selection sort runs in O(N²) time, just as the bubble sort does. However, selection sort is slightly faster because there is less number of swaps in compare to bubble sort. For smaller values of N (input size) the selection sort may in fact be considerably faster, especially if the swap times are much larger than the comparison times.

Last Word

In this tutorial we discussed selection sort. We implemented selection sort algorithm in Java. Selection sort is among the basic and the slowest sorting techniques. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

References