Imagine you have a set of playing cards that you want to sort by size. How would you traditionally start? Exactly – you first choose either the smallest or the largest card, then move on to the next card and repeat the whole thing until all the playing cards are sorted correctly.

The Selection Sort sorting process works in a similar way. But you can find out what else it does differently and how efficient the algorithm really is here.

## Selection sort explanation

So what exactly is selection sort? Selection Sort is an algorithm that sorts data sets through selection. In principle, we always look for either the smallest or the largest element.

The term Selection Sort is made up of the English words selection and sort. That’s why the algorithm is often referred to as “sorting by selection”.

### Selection sort definition

**Selection sort **is a sorting algorithm that repeatedly searches for the smallest or largest element in an array and moves it from the unsorted part to the beginning of the array.

Instead of Selection Sort, we can also talk about Exchange Sort or Selectsort.

## Selection sort algorithm

How exactly does the algorithm behind Selection Sort work? This can best be shown with an example. Given an array that needs to be sorted.

IterationsExecutionSortedUnsortedStep 1Mentally divide the array into a sorted and an unsorted part. The sorted part is initially empty. 5 28497Step 2 Now search the unsorted array for the smallest element. You start with 5, then the array is processed step by step. In the second position you will already find a smaller number with 2, but still go through the rest of the array and see if there is an even smaller number. That is not the case in this example. So swap the 2 with the 5 and move the border between the sorted and unsorted sides one place to the right.**2**58497Step 3Now look for the smallest element (4) in the unsorted part again and swap this number with the one in the second position (5). Then move the whole thing one step to the left again.**2****4**8597Step 4The next step is to swap the 5 and 8 with each other. Then move the border one step to the right again.**2****4****5**897Step 5The next smallest element is the 7. So swap this with the 8 and move the border to the right again.**2****4****5****7**98Step 6Now swap the 8 and 9 with each other and move the border again.**2****4****5****7****8th**9EndThe last element is automatically the biggest, assuming you did everything right. The algorithm is now finished and the array is completely sorted.**2****4****5****7****8th****9**

And that’s it – your array, sorted with Selection Sort, is ready. As you can see, the algorithm basically just goes through the data set and – in this case – always looks for the smallest element, which it then swaps with the first element in the unsorted row.

By the way, the whole thing works the same way if you want to sort in descending order, starting with the largest element. Just that you always look for the largest element in the unsorted part and move it to the beginning.

### Selection sort procedure

A brief summary of how the algorithm works when sorting is to be carried out in ascending order starting with the smallest element:

- Set minimum value to position 0.
- Scan through array to find smallest element.
- If an element is found that is smaller than the previously specified minimum value, swap both values with each other.
- Then take one step to the right.
- Repeat until the array is completely sorted.

## Selection sort complexity

Would you also be interested to know what the complexity of Selection Sort actually looks like?

Selection Sort is a simple sorting algorithm with a squared running time O(n2). This is because the algorithm contains two nested loops.

If the difference between a simple and an efficient sorting algorithm is not clear to you, you can find out more in the explanation of sorting algorithms.

Why two loops? In the first loop, one element of the array is selected individually. The next loop then compares this element with all other elements from the array. Both processes have a complexity of O(n), so the total complexity is O(n) • O(n) = O(n2).

### Space complexity

Sorting elements is done using Selection Sort **in place** – so in place – off. In addition, the algorithm works constantly because no matter how many elements are to be sorted, the same number of auxiliary variables is always required. This means that the space complexity in this case is O(1).

## Selection Slocation – Further terms

In the next sections, other important terms relating to the Selection Sort sorting process will be explained. The following terms are discussed:

- stable vs. unstable
- comparison-based vs. non-comparison-based
- iterative vs. recursive
- Parallelizability

### Selection sort stable – unstable

At first glance, Selection Sort seems stable: If elements with the same value appear in the unsorted part of an array, one should assume that the first of them will also be the first to end up in the already sorted section. However, this is not necessarily the case, as the algorithm may mess up the original order by swapping elements in the unsorted section.

If two elements end up having the same value, the algorithm would not swap them with each other again – because they are already in the correct order. The sorting algorithm is thus **unstable**!

However, it is possible to implement Selection Sort in a stable manner.

#### Selection sort stable

How can selection sort be made stable? You can achieve this by not swapping the elements, but by moving everything between the first and the smallest element one position to the right and putting the smallest element in the front position.

The positive thing is that the running time is generally not affected. However, if an array is searched, the additional shifts result in significantly worse performance. However, for linked lists, this method could be performed without a major performance penalty.

### Selection sort based on comparison

Selection sort is a **comparison-based **Sorting algorithm This means that the algorithm always compares two elements of a data set with each other based on a specific criterion.

### Selection sort iterative – recursive

Selection sort is usually implemented iteratively, but you can also use it recursively. What you should keep in mind: The complexity remains the same as with the iterative variant – i.e. O(n2). However, the space complexity for the recursive variant is O(n) instead of O(1).

As a reminder, O(1) is a constant effort, which means the effort is independent of the number of input elements. O(n), on the other hand, is a linear effort – the effort increases linearly with the number of input elements.

### Selection sort parallelizability

Selection Sort can theoretically be partially parallelized, which means that the outer loop cannot be parallelized, but the inner one can. With the inner loop you could split the array and search for the smallest element in each sub-array in parallel and at the end you merge the results. This doesn’t work with the outer loop because it changes the contents of the array with every step.

All in all, the sorting algorithm is considered not to be parallelizable!

## Selection sort summary

What should you have learned so far? In the overview below you will find a summary of the most important aspects of Selection Sort.

## Selection Sort Advantages – Disadvantages

Since Selection Sort is not the only sorting algorithm in existence, it should be clear that the algorithm has various advantages and disadvantages.

AdvantagesDisadvantagesEasy to understandWorks inefficientlyEasy to implement

But why does the sorting process work rather inefficiently? This is because, in contrast to methods such as Quicksort or Mergesort, a relatively large number of comparisons are necessary. This means that the algorithm works very cost-intensively with its quadratic running time.

“Cost” means the efficiency of the algorithm, i.e. how many runs it takes until a data set is completely sorted.

This is also the reason why the selection sort algorithm is better suited for smaller amounts of data than for larger ones. Because as the data grows, the running time also grows quadratically.

## Selection sort example

To give you a better idea of how Selection Sort works, the following sections will provide you with a few concrete examples.

How and where could Selection Sort be applied? A common example of this is sorting playing cards or generally sorting unsorted sets of numbers.

In general, the sorting algorithm is suitable if:

- small amounts of data should be sorted.
- checking all elements is mandatory.
- the “costs” of the replacement don’t matter.

### Selection sort pseudocode

What could the pseudocode of a selection sort look like? When you enter you will have a list of unsorted data:

Array A of n elements

As output you want to get a sorted list of these elements. The pseudocode for this could e.g. E.g. look like this:

for Element One = 1 to Array Length – 1 do min = Element One for Element Two = Element One + 1 to Array Length – 1 do if Array < Array then min = Element Two end if end for Swap Array and Array end for

In pseudocode, the smallest value is initially set to 1. The outer loop is then looped for as long as Array length – 1 is feasible, i.e. until all values in the array have been processed. Within this loop, another loop searches for a smaller value than the current one. If this is found, the values are then swapped with each other (Swap Array and Array).

### Selection Sort Java

Finally, here is a small example of a selection sort in Java code:

import java.util.Arrays; class SelectionSort { void selectionSort(int array) { int size = array.length; // Move the limit of the unsorted array individually for (int point = 0; point < size - 1; point ++) { int min_idx = point; for (int i = point + 1; i < size; i++) { // selects the smallest element in each loop if (array < array) { min_idx = i; } ...