DEV Community

Fabian Lüdicke
Fabian Lüdicke

Posted on

Selectionsort in Java

Selectionsort is a sorting algorithm that can of course also be implemented in Java. The Selectionsort algorithm is also known as MinSort (from Minimum) or MaxSort (from Maximum), Selectsort or ExchangeSort. What is hidden behind the Selectsort algorithm, how it works and what else there is to know, you will learn now in the following.

Functionality

The functionality of Selectionsort is as follows: You have an array containing the data to be sorted. Now you divide the array into two parts (subarrays). The first part should be the sorted part, the second part the unsorted part. Since nothing is sorted at the beginning, the entire array represents the unsorted part.
Now we look for the smallest element in the array and swap it with the first element. Now the first element is in the sorted part and the remaining elements are in the unsorted part. Now the smallest element is searched for again in the unsorted part and this is now inserted behind the first element in the sorted area. This continues until all elements are in the sorted area and none are in the unsorted area. If you want to sort by size, starting with the largest element, always search for the largest element instead of the smallest. Similar to Simplesort, a remaining subrange of the array is therefore passed through from the front.
Example

Here is an example implementation of the selectionsort algorithm stored in a function, including a test output:

public static void main(String[] args) {

        int[] unsorted = { 4, 2, 1, 6, 3, 5 };
        int[] sorted = selectionsort(unsorted);

        for (int i = 0; i < sorted.length; i++) {
            System.out.print(sorted[i] + ", ");
        }

    }

    public static int[] selectionsort(int[] sorted) {
        for (int i = 0; i < sorted.length - 1; i++) {
            for (int j = i + 1; j < sorted.length; j++) {
                if (sorted[i] > sorted[j]) {
                    int temp = sorted[i];
                    sorted[i] = sorted[j];
                    sorted[j] = temp;
                }
            }
        }

        return sorted;
    }
Enter fullscreen mode Exit fullscreen mode

Runtime

The runtime in the Selectionsort Worst Case corresponds exactly to the complexity in the Best Case. Thus, the Selectionsort runtime is always O(n2). This has a very simple reason, because the list is always run through completely from front to back, regardless of presorted data.

Optimization

An optimization of the selectionsort algorithm is the simultaneous search for the largest and the smallest element in one pass. In this case, the smallest element is moved to the beginning of the array, while the largest is swapped to the last place. This usually gives a speedup by a factor of 2. This one is called "Optimized Selection Sort Algorithm (OSSA)"

Discussion (0)