In this tutorial, we will learn what the **selection sort algorithm** is, how it works, its space and time complexities, and **selection sort implementation in Java**.

**What is Selection Sort Algorithm?**

Selection sort is a sorting algorithm that works by selecting the **biggest number** in an unsorted array and moving it to its final location. In this way, we can sort the array in **ascending order**.

If we want to sort an unsorted array in **descending order** with the selection sort algorithm, this time it selects the **smallest number** and moves it to its final location.

**How Does Selection Sort Work?**

I will explain the Selection sort algorithm in ascending order. Let’s assume that we have an unsorted array as follows: [18, 32, -11, 6, 68, 2, -34]

Our aim is to sort these numbers in **ascending order**. We do the sorting for the **last index** which is called as **indexToBeSorted**. We have **two levels of iterations** which means we have two for loops. The **higher-level for loop starts from indexToBeSorted to index 0** and inside this for loop, we have an **inner for loop that starts from 0 to indexToBeSorted**.

Inside the inner loop, we assume that the **biggest value is located at index 0**, and in each iteration, we find the **“index of the biggest value” by comparisons**. At the end of the iteration, we have the “index of the biggest value” and **we swap the values at “index fo the biggest value” and “indexToBeSorted”**.

Let’s continue with the **visualization of the selection sort algorithm with colorful diagrams.**

**Selection Sort Visualization**

Our unsorted array of numbers is as follows:

And our first **indexToBeSorted** will be **index 6**.

Then **index 5**

Then **index 4**

Then **index 3**

Then **index 2**

Then **index 1**

and finally, all indexes will be sorted.

And for each iteration for the indexToBeSorted:

- We
**iterate from index 0 to indexToBeSorted**. - We assume that the
**index 0 is the “index of the biggest value”**. - We
**compare the values at “index + 1” and the “index of the biggest value”**. - If the value at
**“index[i+1]” is bigger than the value at “index of the biggest value”**, we**assign the “index[i+1]” to “index of the biggest value”**. In this way,**“index[i+1]” becomes the “index of the biggest value”**. - We do these comparisons
**until we reach the indexToBeSorted**. At this point, we**calculated the “index of the biggest value”**and we**swap the values of “index of the biggest value” and “indexTobeSorted”**.

After the first sort iteration for indexToBeSorted, **we decrease the indexTobeSorted by 1 (indexToBeSorted – 1)** and do the same operations while the **indexToBeSorted value is bigger than zero**. In this way, we can sort the unsorted array in ascending order with selection sort.

Let’s visualize the selection sort algorithm with colorful diagrams.

First, I want to explain the meaning of each icon on the diagrams.

**First Iteration**

** **At the first iteration, the **index to be sorted is 6** which was colored by **purple (-34) and** the **“index of the biggest value” (18)** is colored **dark blue.**

Each iteration, the **value at “index of the biggest value” is compared** by the **value at “index + 1”**.

At the end of the iteration, the **“index of the biggest value” is 4 and its value is 68**. We **swap** this value with the **value at indexToBeSorted which is -34**.

In this way, we complete the first iteration.

**Second Iteration**

** **At the second iteration, the **index to be sorted is 5** which was colored by **purple (2) and** the **“index of the biggest value”** **(18)** is colored **dark blue.**

At the end of the iteration, the **“index of the biggest value” is 1 and its value is 32**. We **swap** this value with the **value at indexToBeSorted which is 2**.

**Third Iteration**

** **At the third iteration, the **index to be sorted is 4 **which was colored by **purple (-34) and** the **“index of the biggest value” (18)** is colored **dark blue.**

At the end of the iteration, the **“index of the biggest value” is 0 and its value is 18**. We **swap** this value with the **value at indexToBeSorted which is -34**.

**Fourth Iteration**

** **At the fourth iteration, the **index to be sorted is 3 **which was colored by **purple (6) and** the **“index of the biggest value” (-34)** is colored **dark blue.**

At the end of the iteration, the **“index of the biggest value” is 3 and its value is 6**. We **swap** this value with the **value at indexToBeSorted which is 6 but the values are the same in this case thus our swap implementation does not do anything.**

**Fifth Iteration**

** **At the fifth iteration, the **index to be sorted is 2 **which was colored by **purple (-11) and** the **“index of the biggest value” (-34)** is colored **dark blue.**

At the end of the iteration, the **“index of the biggest value” is 1 and its value is 2**. We **swap** this value with the **value at indexToBeSorted which is -11**.

**Sixth Iteration**

** **At the sixth iteration, the **index to be sorted is 1 **which was colored by **purple (-11) and** the **“index of the biggest value” (-34)** is colored **dark blue.**

At the end of the iteration, the **“index of the biggest value” is 1 and its value is -11**. We **swap** this value with the **value at indexToBeSorted which is -11 but the values are the same in this case thus our swap implementation does not do anything.**

This is the last iteration and we sorted the unsorted array in ascending order with the selection sort algorithm.

**Selection Sort Animation**

**Selection Sort in Java**

I will share with you selection sort implementations in Java with **ascending** and **descending** orders.

**Selection Sort Java Implementation in Ascending Order**

public class SelectionSort { public static void main(String[] args) { int[] array = { 18, 32, -11, 6, 68, 2, -34 }; System.out.println("Ascending Sorted Array: " + Arrays.toString(ascendingSelectionSort(array)) + "\n"); } public static int[] ascendingSelectionSort(int[] array) { Instant start = Instant.now(); //Selection sort with ascending order for (int indexTobeSorted = array.length - 1; indexTobeSorted > 0; indexTobeSorted--) { int indexOfBiggestValue = 0; for (int index = 0; index < indexTobeSorted; index++) { if (array[index + 1] > array[indexOfBiggestValue]) { indexOfBiggestValue = index + 1; } } swap(array, indexOfBiggestValue, indexTobeSorted); } Instant end = Instant.now(); System.out.println("Elapsed time of ascendingSelectionSort: " + Duration.between(start, end).toNanos()); return array; } public static void swap(int[] array, int firstIndex, int secondIndex) { if (firstIndex != secondIndex) { int temp = array[firstIndex]; array[firstIndex] = array[secondIndex]; array[secondIndex] = temp; } } }

**Output**

**Selection Sort Java Implementation in Descending Order**

public class SelectionSort { public static void main(String[] args) { int[] array = { 18, 32, -11, 6, 68, 2, -34 }; System.out.println("Descending Sorted Array: " + Arrays.toString(descendingSelectionSort(array)) + "\n"); } public static int[] descendingSelectionSort(int[] array) { Instant start = Instant.now(); //Selection sort with descending order for (int indexTobeSorted = array.length - 1; indexTobeSorted > 0; indexTobeSorted--) { int indexOfSmallestValue = 0; for (int index = 0; index < indexTobeSorted; index++) { if (array[index + 1] < array[indexOfSmallestValue]) { indexOfSmallestValue = index + 1; } } swap(array, indexOfSmallestValue, indexTobeSorted); } Instant end = Instant.now(); System.out.println("Elapsed time of descendingSelectionSort: " + Duration.between(start, end).toNanos()); return array; } public static void swap(int[] array, int firstIndex, int secondIndex) { if (firstIndex != secondIndex) { int temp = array[firstIndex]; array[firstIndex] = array[secondIndex]; array[secondIndex] = temp; } } }

**Output**

**The Complexity of Selection Sort**

In this part, I will explain the time and space complexity of the selection sort algorithm.

**Time Complexity**

In the selection sort algorithm, **we do comparisons between “index of biggest value” and “index + 1” in each iteration for the index to be sorted**. Let’s say the length of the array is n.

Number of comparisons become:

**(n-1) + (n-2) + (n-3) +…..+ 1 = n(n-1)/2**

Which is approximately the **n ^{2}**. Hence, the

**time complexity is O(n**

^{2}) in BigO notation.As you also saw that we have two iterations (two for loops) which is also another way to show us Selection Sort has** n*n=n ^{2 }**time complexity.

**Worst Case Time Complexity of Selection Sort**

When we do a sort in ascending order and the array is ordered in descending order then we will have the worst-case scenario. In this case, the **worst-case complexity** will be** O(n ^{2})**.

**Best Case Time Complexity of Selection Sort**

When we do a sort in ascending order and the array is also already ordered in ascending order then we will have the best-case scenario because the array is already ordered as we wanted. In this case, the **best-case complexity** will be **O(n ^{2}) **too because we will have two for loops (iterations).

**Space Complexity**

The space **complexity of the Selection sort is O(1)**. We use only indexOfBiggestValue for ascending sorting and indexOfSmallestValue for descending sorting.

**When Can We Use Selection Sort?**

Selection sort is a simple and inefficient sorting algorithm. Its time complexity is not the best one. Thus, it can be used when the running time does not matter and when we work with a small dataset.

**GitHub Project**

Selection Sort Implementation in Java

In this article, I have shared what selection sort is, how it works, its complexities, and its implementations. I also tried to visualize the selection sort algorithm with colorful diagrams to make it as clear as possible. I hope you enjoyed reading this article.

**Other Sorting Algorithms Articles**

See you in another article,

Onur Baskirt

Onur Baskirt is a senior IT professional with 15+ years of experience. Now, he is working as a Senior Technical Consultant at Emirates Airlines in Dubai.