Simple sort
Simplesort is not stable in-place - sorting method that the SelectionSort similar. For an array of length n, simple sort has a time expenditure of O (n 2 ) in Landau notation . Simplesort is a particularly simple algorithm .
The intuitive idea behind Simplesort is that you look at the positions in the array to be sorted one after the other (outer loop) and look for the element belonging to it (inner loop) and sort them there. Selectionsort uses the same principle, but with Simplesort there can be several interchanges of two elements for each position that is considered in the outer loop, until the correct element is at this position. Selectionsort first determines the index of the correct element and then only makes a swap to put it in its place.
algorithm
myArray is the array to be sorted (indices from 1 to N).
Schleife über zielPos = 1 .. N-1
{
// Suche kleinere Elemente im nachfolgenden, noch unsortieren Bereich:
Schleife über pruefPos = zielPos+1 .. N
{
Falls myArray[pruefPos] < myArray[zielPos] dann
{
Vertausche myArray[pruefPos] mit myArray[zielPos]
}
}
}
Explanation
The elements are sorted in ascending order here. In the first outer loop pass, targetPos = 1, i.e. the first position in myArray. The inner loop now checks all subsequent positions in myArray ( checkPos from targetPos +1 to N) whether there is a smaller value than targetPos , and if such a value is found, it is exchanged with position targetPos . If an even smaller value is found later in the inner loop, it is swapped to the position targetPos , and the lower value there ends up further back. After all, the smallest value is right at the front at targetPos = 1.
In the next iteration of the outer loop, the second position in the array is considered: targetPos = 2. In the area behind (3 to N), a smaller element is now sought and, if necessary, placed at position 2. The two smallest values are then in their final position.
The fully sorted starting area of the array increases by one with each iteration of the outer loop until the array is completely sorted.
It is just as possible to reverse the running directions of the loops. When the outer loop descends, the largest element in each case must be searched for in the remaining unsorted area (1 to targetPos -1).