Selection Sort Algorithm in Java | Visualization and Examples

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². Hence, the time complexity is O(n²) 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²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²).

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²) 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.