Selection Sort - Sorting Algorithms

In selection sort algorithm the whole array is divided into two sub arrays one is sorted and another one is unsorted. We find (select) the minimum element form the unsorted sub array and swap it with the element at the starting index of the unsorted sub array. This way this elements becomes a part of the sorted sub array and size of sorted sub array increases by one and unsorted array decreases by one. We keep repeating this process until all the elements in unsorted sub array are exhausted.

Let’s try to understand Selection sort with the help of an example -
Suppose we want to sort an array - {11, 21, 22, 2, 14, 3, 22, 21, 99, 77}

Initially all the elements in the given array are considered in unsorted sub array.
So we will start from the very first element of the array and search the minimum element in this array which is 2 in this case.
Now we will swap the element '2' with the very first element of unsorted sub array which is element '11'.
After swapping the elements our new array will look something like this -
{2, 21, 22, 22, 14, 3, 22, 21, 99, 77}
Now we can see that whole array has been divided into two subarrays with one element (2) in sorted subarray and rest of the elements in the unsorted subarray.
In next iteration we will again find the minimum element in the unsorted sub array and swap it with the first element of the unsorted subarray which is 21. This will again increase the size of sorted sub array by one.

We will keep repeating this process for all the elements of unsorted sub array and in the end we will see that we are left with only one array which is sorted.

Let’s write a Java program for Selection Sort Algorithm :

package algo.sorting;

public class SelectionSort {
public static int[] sort(int[] arr) {
  int n = arr.length;

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

 public static void main(String args[]) {
  int[] arr = { 11, 21, 11, 23, 1, 34, 221, 3, 455, 6 };
  
  System.out.println("Unsorted Array -");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
  
  arr = sort(arr);
  
  System.out.println();
  System.out.println("Sorted Array After Selection Sort -");
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }
}

Unsorted Array -
11 21 11 23 1 34 221 3 455 6 
Sorted Array After Selection Sort -
1 3 6 11 11 21 23 34 221 455