### 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