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.

Selection Sort 1

This is our input.

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

Selection Sort 2

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

Selection Sort 3

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

Selection Sort 4

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.

Selection Sort 5

After 2nd pass the first 2 elements are sorted.

Selection Sort 6

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.

Selection Sort 7

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

Selection Sort 8

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.

Selection Sort 9

After 4th pass 4 elements are sorted.

Selection Sort 10

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.

Selection Sort 11

After 5th pass 5 elements will be sorted.

Selection Sort 12

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.

Selection Sort 13After swapping 6 elements are sorted.

Selection Sort 14

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

Selection Sort 15

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.

Disadvantages

Always even if array is already sorted then also comparisons will be in O(n^2) only.

Comment below if you have doubts related to selection sort in Java.

Leave a Reply

Your email address will not be published. Required fields are marked *