Selection Sort in Java

Selection Sort is a comparison-based sorting algorithm that sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. The process is continued until the entire array is sorted.

Algorithm for Selection Sort

Step 1 : Set the first element as minimum.
Step 2 : Compare minimum with the second element. If the second element is smaller than minimum, assign the second element as minimum. Compare minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. The process goes on until the last element.
Step 3 : After each iteration, minimum is placed in the front of the unsorted list.
Step 4 : For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until all the elements are placed at their correct positions.

Selection Sort Algorithm Syntax

selectionSort(array, size)
  for i from 0 to (size - 1) do
    set i as the index of the current minimum
    for j from (i + 1) to (size - 1) do
      if array[j] < array[current minimum]
        set j as the new current minimum index
    if current minimum is not i
      swap array[i] with array[current minimum]
end selectionSort

Selection Sort Complexity

Time Complexities:

Worst Case Complexity: O(n2)
when the array we want to sort is in descending order then, the worst case occurs.

Best Case Complexity: O(n2)
It occurs when the array is already sorted

Average Case Complexity: O(n2)
When the array is neither in ascending nor descending order,time complexity is O(n2)

Space Complexity: O(1)

Space complexity is O(1) because an extra variable min_index is used.

Selection Sort Applications

The selection sort is used when

1) Suitable for small lists
2) cost of swapping does not matter
3) checking of all the elements is mandatory
4) Ideal for systems with limited memory like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)
5) Used in simple embedded systems where resource availability is limited

Program : Selection Sort in Java

import java.util.Arrays;

public class Selection_Sort_Prog {

	public static void selectionSort(int arr[]) {
	    int n = arr.length;

	        for (int i = 0; i < n - 1; i++) {
	          
	            int min_index = i;
	          
	            for (int j = i + 1; j < n; j++) {
	                if (arr[j] < arr[min_index])
	                    min_index = j;
	            }

	            int temp = arr[min_index];
	            arr[min_index] = arr[i];
	            arr[i] = temp;
	        }
	  }

	  public static void main(String args[]) {
	    int[] data = { 40, 18, 12, 56, 27,76 };
	    Selection_Sort_Prog select_obj = new Selection_Sort_Prog();
	    select_obj.selectionSort(data);
	    System.out.println("Sorted Array in Ascending Order: ");
	    System.out.println(Arrays.toString(data));
	  }
}

Output :

Sorted Array in Ascending Order: 
[12, 18, 27, 40, 56, 76]