Selection location
Selection sort ( English selection 'selection' and English sort 'sort') is a simple ("naive") sorting algorithm that works inplace 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).
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
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.

The minimum is 1. So swap the 1st and 3rd element.  

The minimum of the right subarray is 2. Since it is already in the 2nd position, it is not swapped.  

We already have a sorted subarray of length 2. We now swap 4 and the minimum 3.  

We swap 6 and 4.  

We swap 6 and 5.  

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.
The first time the minimum is determined, comparisons are necessary; the second, comparisons, etc.
The number of necessary comparisons is obtained with the Gaussian empirical formula :
Since is the first element , the exact number of steps does not exactly match the representation of the Gaussian formula .
SelectionSort is therefore in the complexity class .
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" .
Web links
 VisuSort Framework  visualization of various sorting algorithms (Windows)
 http://www.sortieralgorithmen.de/selectsort/index.html
 Explanation and code in C ++

OSSA  Presentation and pseudocode (PDF)
OSSA bugfixed