# Selection Sort in Java

In this tutorial you will learn about selection sort in Java with example.

It will sort the input elements in ascending or descending order by taking small or large element among the input elements and swap that element with the element in 1st position. Then it picks second small or large element and swap it with the element in second position. Likewise it will sort all the elements in the input in n-1 passes if our input size is n. While doing this process the input will be seemed as two parts one is sorted and other one is unsorted.

Now we will see the selection sort algorithm with an example.

Let us apply selection sort algorithm on an array with 7 elements.

This is our input.

Pass 1: picking the smallest element. It will scan entire array from left to right and picks the smallest element.

After that it will swap the small element with the element at first index.

After 1st pass our array will look like this. And after 1st pass 1 element will be sorted from left hand side.

Pass 2: In second pass it will start from the 2nd index and start searching for smallest element in the remaining array. First smallest element is already sorted in 1st pass. Now it will get second smallest element. It will swap with the second element from the left.

After 2nd pass the first 2 elements are sorted.

Pass 3: In third pass it will start form 3rd element and scan the remaining array for the smallest element. It will swap this element with the third element from the left.

After 3rd pass first three elements will be sorted from left.

Pass 4: In 4th pass it will start form 4th element and scan the remaining array for smallest element and swap with the 4th element.

After 4th pass 4 elements are sorted.

Pass 5: In 5th pass it will start from 5th element and scan the remaining array for smallest element. It will swap with the 5th element form left.

After 5th pass 5 elements will be sorted.

Pass 6: In pass 6 it will start with 6th element and scan the remaining array for next smallest element and it will swap with the 6th element.

After swapping 6 elements are sorted.

Here n-1 passes are completed. Our array is completely sorted. We need not to go for one more pass.

## Program for Selection Sort in Java

Output

array before sorting
4 5 6 7 1 2 3

array after sorting
1 2 3 4 5 6 7

Time Complexity Analysis

For sorting n elements it is taking n-1 passes. In each pass it will scan entire array it will take O(n) time. Total n*O(n) that is O(n^2).

Importance of Selection Sort

It is a comparison based sort. It is famous for simplicity of algorithm and implementation. It always outperforms bubble sort. If we observe selection sort algorithm it will take O (n^2) time. But for smaller inputs it is better than other sorting which have time complexity O (nlogn). Some of n(logn) algorithms now shifting towards selection sort and insertion sort when the input is less than some threshold.

In selection sort, swapping will be always O(n) only. If we want to minimize the writes to memory then selection sort will give us better results.