**I just announced the new *** Learn Spring * course, focused on the fundamentals of Spring 5 and Spring Boot 2:

*Learn Spring*course, focused on the fundamentals of Spring 5 and Spring Boot 2:

**>> CHECK OUT THE COURSE**

Last modified: August 13, 2019

In this tutorial, we’ll **learn Selection Sort**, see its implementation in Java, and analyze its performance.

Selection Sort **begins with the element in the 1 ^{st} position of** an unsorted array and scans through subsequent elements to

The algorithm then moves on to the element in the 2^{nd} position and scans through subsequent elements to find the index of the 2^{nd} smallest element. Once found, the second smallest element is swapped with the element in the 2^{nd} position.

This process goes on until we reach the n-1^{th} element of the array, which puts the n-1^{th} smallest element in the n-1^{th} position. The last element automatically falls in place, in the n-1^{th} iteration, thereby sorting the array.

We find** the largest element instead of the smallest element to sort the array in descending order.**

Let’s see an example of an unsorted array and sort it in ascending order to visually understand the algorithm.

Consider the following unsorted array:

*int[] arr = {5, 4, 1, 6, 2}*

**Iteration 1**

Considering the above working of the algorithm, we start with the element in 1^{st} position – 5 – and scan through all subsequent elements to find the smallest element – 1. We then swap the smallest element with the element in 1^{st} position.

The modified array nows looks like:

*{1, 4, 5, 6, 2}*

Total comparisons made: 4

**Iteration 2**

In the second iteration, we move on to the 2^{nd} element – 4 – and scan through subsequent elements to find the second smallest element – 2. We then swap the second smallest element with the element in 2^{nd} position.

The modified array now looks like:

*{1, 2, 5, 6, 4}*

Total comparisons made: 3

Continuing similarly, we have the following iterations:

**Iteration 3**

*{1, 2, 4, 6, 5}*

Total comparisons made: 2

**Iteration 4**

*{1, 2, 4, 5, 6}*

Total comparisons made: 1

Let’s implement Selection Sort using a couple of *for* loops:

public static void sortAscending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minElementIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[minElementIndex] > arr[j]) { minElementIndex = j; } } if (minElementIndex != i) { int temp = arr[i]; arr[i] = arr[minElementIndex]; arr[minElementIndex] = temp; } } }

Of course, to reverse it we could do something quite similar:

public static void sortDescending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int maxElementIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[maxElementIndex] < arr[j]) { maxElementIndex = j; } } if (maxElementIndex != i) { int temp = arr[i]; arr[i] = arr[maxElementIndex]; arr[maxElementIndex] = temp; } } }

And with a bit more elbow grease, we could combine these using *Comparator*s.

In the example that we saw earlier, **selecting the smallest element required a total of (n-1) comparisons** followed by swapping it to the 1

Thus, starting from index 0, we perform *n-1, n-2, n-3, n-4 …. 1* comparisons. The last element automatically falls in place due to previous iterations and swaps.

Mathematically, the **sum of the first n-1 natural numbers **will tell us how many comparisons we need in order to sort an array of size

**The formula for the sum of n natural numbers is n(n+1)/2.**

In our case, we need the sum of first *n-1* natural numbers. Therefore, we replace *n* with *n-1* in the above formula to get:

*(n-1)(n-1+1)/2 = (n-1)n/2 = (n^2-n)/2*

As *n^2* grows prominently as *n* grows, we consider the higher power of *n* as the performance benchmark, making this algorithm have a **time complexity of O(n^2).**

In terms of auxiliary space complexity, Selection Sort requires one extra variable to hold the value temporarily for swapping. Therefore, Selection Sort’s **space complexity is O(1).**

Selection Sort is a very simple sorting algorithm to understand and implement. Unfortunately, **its quadratic time complexity makes it an expensive sorting technique**. Also, since the algorithm has to scan through each element, **the best case, average case, and worst-case time complexity is the same**.

Other sorting techniques like Insertion Sort and Shell Sort also have quadratic worst-case time complexity, but they perform better in best and average cases.

Check out the complete code for Selection Sort on GitHub.

## Leave a Reply