Selection location

from Wikipedia, the free encyclopedia

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).

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.

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.

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

Wikibooks: Selectionsort  - implementations in the algorithm collection