Selection Sort Algorithm

Selection sort is a selection process to find the smallest element repeatedly from the list of elements is kept. We find the smallest number and keep it in the beginning. The algorithm of selection sort maintains two types of arrays which are:

• An array that is already in the sorted form.
• An array that is yet to be sorted.

We take the smallest element from the unsorted list of elements in each iteration. It is then moved to the list which is sorted. Below is an example of how we can follow iterations for selection sort algorithm:

Read Core Java Interview Questions

Step 1: We have an array of 4 elements arr[0,3]:

23, 56, 11, 27

Step 2: We find the smallest element and we move it to the beginning. The smallest element is 11 so we move it.

The array becomes:

11, 56, 23, 27

Step 3: now we find the next smallest element after 11 which is 23 in the array.

Move 23 in the array of sorted elements. The array becomes:

11, 23, 56, 27

Step 4: in the similar way when we check the next smallest element after 23, it is 27. So we move it to the list of sorted elements.

11, 23, 27, 56

As we check we get the sorted list of elements.

So the list becomes: arr[11, 23, 27, 56]

To write an algorithm for the above sorting process, check the steps below:

• Set MIN to 0 location and place it in arr[0].
• Search the smallest element in the list
• Swap the smallest element with the original location of MIN
• Increment MIN to move to the next element.
• Repeat these steps till the list is sorted.

Selection Sort Program in Java

import java.util.Scanner;  
  public class DeveloperHelps  
{  
   public static void main(String args[])  
   {  
       int size, i, j, temp;  
       int arr[] = new int[50];  
       Scanner scan = new Scanner(System.in);  
         
       System.out.print("Enter the size of array");  
       size = scan.nextInt();  
        System.out.print("Enter the eleemnts of array");  
       for(i=0; i<size; i++)  
       {  
           arr[i] = scan.nextInt();  
       }      
       System.out.print("Performing selection sort");  
       for(i=0; i<size; i++)  
       {  
           for(j=i+1; j<size; j++)  
           {  
               if(arr[i] > arr[j])  
               {  
                   temp = arr[i];  
                   arr[i] = arr[j];  
                   arr[j] = temp;  
               }  
           }  
       }  
       System.out.print("The sorted list is");  
       for(i=0; i<size; i++)  
       {  
           System.out.print(arr[i]+ "  ");  
       }  
   }  
}

The output of the above program will be:

Enter the size of array 3
Enter the elements of array 23 11 56 27
Performing selection sort
The sorted list is 11 23 27 56

The best and average time complexity of this algorithm is (n^2) and the worst time complexity is O(n^2). However, the space complexity is O(1).