Selection Sort Algorithm - The Coding Shala

Home >> Algorithms >> Selection Sort

 In this post, we will learn what is Selection Sort Algorithm and how to implement Selection Sort in Java.

Selection Sort Algorithm

The selection sort algorithm is a sorting algorithm that sorts an array by repeatedly finding minimum element(ascending order)/maximum element(descending order) from the unsorted part and put it at the beginning of the unsorted array. This algorithm maintains two subarrays in a given array, one is sorted and the second is the remaining unsorted subarray.

Working of Selection Sort Algorithm

We follow the below steps to implement the Selection Sort Algorithm:
  • Step 1. We pick the minimum element from the unsorted subarray.
  • Step 2. Swap it with the first element of the unsorted subarray.
  • Step 3. Now the first element of unsorted subarray becomes a part of the sorted subarray.
Here is an example that explains the selection sort algorithm:

Array:  64 25 12 22 11
       key = 64
       min = 11
after swap: 11 25 12 22 64

  key = 25
  min = 12
after swap: 11 12 25 22 64

   key = 25
   min = 22
after swap: 11 12 22 25 64

     key = 25
   min = 25
 
     final sorted array: 11 12 22 25 64

The time complexity of Selection Sort

The time complexity of the selection sort is O(n^2). There are two nested loops. one for finding min another for every element.

In the selection sort algorithm, the auxiliary space is O(1).

Selection Sort Algorithm Java Program

The following is the Java Program of Selection Sort Algorithm.

Java Program: 

import java.util.Arrays;

//selection sort
//the coding shala

class Main{
	
	public static void selection_sort(int[] input) {
		for(int i=0;i<input.length;i++) {
			int min_index = i;
			//find minimum element 
			for(int j=i+1; j<input.length; j++) {
				if(input[j]<input[min_index]) {
					min_index = j;
				}
			}
			
			//swap minimum element
			int tmp = input[min_index];
			input[min_index] = input[i];
			input[i] = tmp;
		}
	}
	
	public static void main(String[] args) {
		int[] input = {1,5,3,2,8,7,6,4};
		int len = input.length;
		selection_sort(input);
		for(int i=0;i<len;i++) {
			System.out.print(input[i]+" ");
		}
	}
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala