Selection sort algorithm Java

Selection sort algorithms are used to reorder the elements of an array or list in ascending or descending numerical or lexicographic order. Sorting is very important for the optimal performance of other algorithms that require sorted input data.

There are a number of different sorting algorithms. The selection of an appropriate algorithm depends on factors such as the size and characteristics of the input data, available memory, and time and space requirements.

To make your choice easier, in our series we will introduce the most well-known data sorting algorithms, explain their principles, advantages and disadvantages, and implement them in Java. So far, we have discussed the following sorting algorithms:

• Sorting algorithms: an introduction to data sorting,
• Bubble sort,
• Comb sort,
• Big O notation: analyzing the complexity of algorithms.

Today we are going to look at selection sort.

Selection sort algorithm

Sort by selection is a simple data sorting algorithm that divides the input field into two parts: sorted and unsorted.
It then repeatedly selects the smallest (largest) element from the unsorted part and moves it to the sorted part.
The algorithm is very inefficient for a large number of elements in the input, but it is often used in situations where there are relatively few elements in the input, most often in combination with other sorting algorithms.

How selection sort algorithm works (step by step)?

Suppose we want to sort the input vector from the smallest to the largest element. For reverse sorting, the whole logic of the algorithm is inverted. The sorted part of the array is always empty at the beginning of the algorithm.

1. At the beginning of the algorithm, we assume that the first element (of the unsorted part) is the minimum (i.e., the smallest).
2. We compare this element with the remaining elements in the unsorted part of the array and look for the true smallest element.
3. If we find a minor element in the unsorted part, we replace the elements.
4. The replaced element becomes part of the sorted dataset, its index is increased by 1 and the unsorted part is decreased.
5. Repeat steps 1 to 4 until the entire field is sorted.

We will then show a practical example in Java code.

Selection sort advantages

• It is easy to understand and implement,
• works well for small lists of data.

Selection sort disadvantages – how selection sort is unstable, time complexity, intensity

• The time complexity is O(n²), which makes it a slow algorithm for a large dataset,
• is not stable.

Selection sort time intensity

Selection sort animation, visualization, gif

A visualization of the Selection sort algorithm looks like this:

Source: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms

You can find an animation of the algorithm for example at Toptal. There are 8 types of algorithms, you can also play the animation backwards. On this page you can go through the steps of the algorithm to check the time consumption of the algorithm.

Selection sort Java implementation

Having familiarized ourselves with the principles of the algorithm, we can now program it in Java. SelectionSort.java

package sorting;

public class SelectionSort {
    private boolean change;
    private int temp;

    public void sort(int data[])
    {
        for (int i = 0; i < data.length - 1; i++) {
            System.out.println(i + 1 + ". iteration");
            // Find the index of the minimum in unsorted part of array
            int minIndex = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[minIndex])
                    minIndex = j;
            }

            // Swap the minimum element with first element from unsorted part, unless they are the same
            if(i != minIndex) {
                System.out.print("Found minimum: " + data[minIndex] + ", swapping with " + data[i] + " => ");
                temp = data[minIndex];
                data[minIndex] = data[i];
                data[i] = temp;
            }
            else
                System.out.print("Minimum: " + data[minIndex] + " is on the right spot, no swapping => ");
            printArray(data);
        }
    }

    // Function to print an array
    public void printArray(int data[])
    {
        for (int i = 0; i < data.length; i++)
            System.out.print(data[i] + " ");
        System.out.println();
    }
}

Main.java

import sorting.SelectionSort;

public class Main {
    public static void main(String[] args) {
        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
        SelectionSort selectionSort = new SelectionSort();
        System.out.print("Input: ");
        selectionSort.printArray(dataToSort);
        selectionSort.sort(dataToSort);
        System.out.print("Sorted: ");
        selectionSort.printArray(dataToSort);
    }
}

The output of this example is: We have prepared the files with the above example in the form of code that you can run directly in Java. Download SelectionSort Java code. If you’re a Java programmer looking for work, check out our employee benefits and respond to our latest job openings.

About the author

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.