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