**Get started with Spring 5 and Spring Boot 2, through the ***Learn Spring* course:

*Learn Spring*course:

**>> CHECK OUT THE COURSE**

Last modified: September 7, 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 over on GitHub.

Follow the Java Category

Follow the Java category to get regular info about the new articles and tutorials we publish here.