Selectionsort

The term selection sort (English selection, selection ' and English sort, sort ') denotes a naive sorting algorithm works in-place and is unstable in its basic form, where it can be implemented also stable. The complexity of selection sort is expressed in the Landau notation. Alternative names of the algorithm are MinSort (from minimum) or MAXSORT (of maximum), SelectSort or ExchangeSort ( AustauschSort ).

Principle

Let S be the sorted part of the array and U is the unsorted part. At the beginning of S is empty, U corresponds to the entire array. Sorting by selecting works like this:

Find the smallest element in U and Swap it with the first element.

After the array is sorted up to this position. The smallest element is moved to S. S has grown by an element U become shorter by one element. Then the process is repeated until the entire array has been processed.

Alternative searches to the maximum, so the element with the largest sort key. The maximum is then swapped with the last element of the array and also obtained a sorted subarray of length 1, but the right, and an unsorted array of length n-1, this time on the left. The algorithm is then applied to the unsorted array part.

In addition, approaches in which both variants ( MinSort and MAXSORT ) work together exist, that is sought is the largest and the smallest element of an array during a run and this will then set respectively at the beginning or at the end of the array. This achieves, as a rule, an acceleration by a factor of 2

Formal algorithm

The algorithm looks in pseudocode as follows:

Procedure SelectionSort (A: list of sortable items )    n = length (A)    left = 0    repeat      min = left      repeat for each i from left 1 to n        when A [i]

There is an array to be sorted with the content. Red colored fields indicate a swap operation, blue colored fields lie in the already sorted part of the array.