# Selection location

Selection sort ( English selection 'selection' and English sort 'sort') is a simple ("naive") sorting algorithm that works in-place and is unstable in its basic form , although it can also be implemented in a stable manner. The complexity of selection sort is ( Landau notation ). Alternative names of the algorithm are MinSort (from minimum ) or MaxSort (from maximum ), Selectsort or ExchangeSort (exchangeSort). ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

## principle

Let S be the sorted part of the array (in front of the array) and U the unsorted part (behind). At the beginning S is still empty, U corresponds to the whole (remaining) array. Sorting by selecting now works as follows:

Find the smallest element in U and swap it with the first element of U (= the first element after  S).

The array is then sorted up to this position. The smallest element is shifted in S (by simply considering S one element longer and U now starting one element later). S has grown by one element, U has become one element shorter. The process is then repeated until the entire array has been processed; At the end S comprises the entire array, sorted in ascending order, U is empty.

### Alternatives

Similarly, instead of the smallest element, the largest in U can be searched for, which leads to a descending sort order. U can also be put to the front and S to the back, which also reverses the sorting order.

In addition, there are approaches in which both variants (MinSort and MaxSort) work together; there is an S area at the front and an S area at the back, with U in between. During one pass, the largest and smallest element in U are searched for and these are then placed at the beginning and end of U respectively. This usually results in an acceleration, which, however, usually does not reach a factor of 2. This variant is sometimes called the "Optimized Selection Sort Algorithm" (OSSA).

## Formal algorithm

The algorithm looks like this in the pseudocode :

prozedur SelectionSort( A : Liste sortierbarer Elemente )
hoechsterIndex = Elementanzahl( A ) - 1
einfuegeIndex = 0
wiederhole
minPosition = einfuegeIndex
für jeden idx von (einfuegeIndex + 1) bis hoechsterIndex wiederhole
falls A[ idx ] < A[ minPosition ] dann
minPosition = idx
ende falls
ende für
vertausche A[ minPosition ] und A[ einfuegeIndex ]
einfuegeIndex = einfuegeIndex + 1
solange einfuegeIndex < hoechsterIndex
prozedur ende


## example

The algorithm has to go through the unsorted part of the field each time to find the smallest element.

An array is to be sorted with the content . Fields colored red indicate an exchange operation, fields colored blue are in the already sorted part of the array. ${\ displaystyle [4 | 2 | 1 | 6 | 3 | 5]}$

 4th 2 1 6th 3 5
The minimum is 1. So swap the 1st and 3rd element.
 1 2 4th 6th 3 5
The minimum of the right subarray is 2. Since it is already in the 2nd position, it is not swapped.
 1 2 4th 6th 3 5
We already have a sorted sub-array of length 2. We now swap 4 and the minimum 3.
 1 2 3 6th 4th 5
We swap 6 and 4.
 1 2 3 4th 6th 5
We swap 6 and 5.
 1 2 3 4th 5 6th
The array is now sorted.

## complexity

To sort an array with entries using SelectionSort, the minimum must be determined times and swapped just as often. ${\ displaystyle n}$${\ displaystyle n-1}$

The first time the minimum is determined, comparisons are necessary; the second, comparisons, etc. ${\ displaystyle n-1}$${\ displaystyle n-2}$

The number of necessary comparisons is obtained with the Gaussian empirical formula :

${\ displaystyle (n-1) + (n-2) + \ dotsb + 3 + 2 + 1 = {\ frac {(n-1) \ cdot n} {2}} = {\ frac {n ^ {2 }} {2}} - {\ frac {n} {2}}}$

Since is the first element , the exact number of steps does not exactly match the representation of the Gaussian formula . ${\ displaystyle n-1}$${\ displaystyle n + (n-1) + \ dotsb + 2 + 1 = {\ tfrac {n \ cdot (n + 1)} {2}}}$

SelectionSort is therefore in the complexity class . ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

Since the entire, not yet sorted part of the array has to be run through to determine the minimum, SelectionSort also needs comparisons in the "best case" . ${\ displaystyle {\ tfrac {n \ cdot (n-1)} {2}}}$