Selection Sort in Java

Today we will discuss yet another sorting algorithm which also falls among the simplest and used heavily in beginner's level.
Selection Sort as the name suggests is based on the logic of finding the smallest elements among the compared elements in its phase.

Let me make it more clear by an example.

If given numbers are 2,5,3,4,1, in the first phase the smallest among the 5 numbers i.e 1 will be found and placed in the 1st position. In second phase we will compare the others elements and smallest among them i.e 2 will be placed in 2nd position. Like wise after the 5th phase all the 5 elements all being sorted.

You can also have a look on the below GIF for better understanding.


Let get hands on by writing a simple Java program to sort elements using Selection Sort.

import java.util.Arrays;

public class SelectionSort {

 public static void main(String[] args) {
        
        int arr[] = {12, 11, 13, 5, 6};
 
        SelectionSort ss = new SelectionSort();  
        System.out.println("Array before sort " + Arrays.toString(arr));
        ss.sort(arr);
        System.out.println("Array after sort " + Arrays.toString(arr));

 }

 private void sort(int[] list) {
  //First loop to change the index number
  for (int i = 0; i < list.length - 1; i++) {        // the last item doen't need to do the loop to compare
   // set the first item as index number
   int currentMin = list [i] ;
   int currentMinIndex = i;
   // second loop to do comparison with the number after it
   for (int j = i + 1; j < list.length; j++) { 
    // if there's number (that locates behind the index number) bigger than the index number
    if (currentMin > list [j] ) {

     // change the currenMin value to the new min number
     currentMin = list [j] ;

     // change the index
     currentMinIndex = j ;
    }
   } 
   // swap the value of the index number with the new min number
   if (currentMinIndex != i) {
    list [currentMinIndex] = list [i] ; 
    list [i] = currentMin ;
   }
  }
 }
}

Analysis of Selection Sort

• Worst and Average Case Time Complexity: O(n*n). 
• Best Case Time Complexity: O(n*n). Best case occurs when array is already sorted.
• Auxiliary Space: O(1)
• Sorting In Place: Yes

Hope you like it. Please stay tune as we will discuss some more interesting and efficient sorting algorithms in coming tutorial. Please comment on any doubts.

Happy Learning !!!

SHARE

Onlinecodegeek