Selection sort in Java

1. Overview

In this article, we will learn about the selection sort in Java. To learn more about data structures, refer to our articles.

2. Selection sort

Assume you have a list of integers that need to be sorted in ascending order.

We look for the smallest element in the list and swap it with the element at the index 0. We then look for the next smallest element and swap it with the element at index 1. The process continues until we sort all the elements in the list.

We have to write a nested loop and so would take O(n^2) operations.

Selection sort is a neat algorithm, but it’s not fast taking O(n^2) whereas quicksort is a faster sorting algorithm that only takes O(n log n) time.

Look at the following code.

We have to iterate each element on the list. This takes O(n) time, if you see the parent for loop in the code. So you have an operation that takes O(n) time, and you compare each element with other elements in the list (n times) and swap it.

This takes O(n × n) time or O(n2) time.

@Test
    void selectionSortExample() {
        int[] list = new int[] {2, 8, 76, 89, 54};
        System.out.println(Arrays.toString(selectionSort(list)));
    }

    private int[] selectionSort(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < arr.length; j++){
                if (arr[j] < arr[index]){
                    index = j;
                }
            }
            int smallerNumber = arr[index];
            arr[index] = arr[i];
            arr[i] = smallerNumber;
        }
        return arr;
    }

2.1. Selection sort Java Big O notation

A selection sort takes O(n^2). Now you may wonder, the number of elements you have to check keeps decreasing for each iteratory. Eventually, you’re down to having to check just one element. So how can the run time still be O(n^2).

It is because the Big O notation ignores constants. You’re right that you don’t have to compare every element with a list of n elements each time. You check n elements for the first iteration, then n – 1, n - 2 … 2, 1.

On average, you check a list that has 1/2 × n elements. The runtime is O(n × 1/2 × n). Since we ignore constants like 1/2 in Big O notation, so you just write O(n × n) or O(n2).

3. Conclusion

To sum up, we have learned the selection sort in Java. You can find the code samples in our GitHub repository.