Doppelte Auswahlsortierung – eine Unterart der Auswahlsortierung, die anscheinend doppelt so schnell sein sollte. Der Vanilla-Algorithmus durchläuft die Liste der Zahlen doppelt, findet die Mindestzahl und tauscht die Plätze mit der aktuellen Zahl, auf die die Schleife auf der Ebene darüber zeigt. Die Sortierung mit doppelter Auswahl sucht nach den minimalen und maximalen Zahlen und ersetzt dann die beiden Ziffern, auf die die Schleife auf der Ebene darüber zeigt – zwei Zahlen links und rechts. Diese ganze Orgie endet, wenn die Cursor der zu ersetzenden Zahlen in der Mitte der Liste gefunden werden und als Ergebnis sortierte Zahlen links und rechts von der visuellen Mitte erhalten werden.
Die zeitliche Komplexität des Algorithmus ähnelt der von Selection Sort – O(n2), aber angeblich gibt es eine Beschleunigung von 30 %.
Grenzzustand
Bereits in diesem Stadium können Sie sich den Moment einer Kollision vorstellen, zum Beispiel, wenn die Zahl des linken Cursors (die Mindestzahl) auf die Höchstzahl in der Liste zeigt, dann wird die Mindestzahl neu angeordnet, die Neuordnung der Höchstzahl bricht sofort zusammen. Daher beinhalten alle Implementierungen des Algorithmus die Prüfung auf solche Fälle und das Ersetzen von Indizes durch korrekte. In meiner Implementierung hat eine Prüfung gereicht:
maximalNumberIndex = minimalNumberIndex;
}Реализация на Cito
Cito – язык либ, язык транслятор. На нем можно писать для C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, при этом совершенно ничего не зная про эти языки. Исходный код на языке Cito транслируется в исходный код на поддерживаемых языках, далее можно использовать как библиотеку, либо напрямую, исправив сгенеренный код руками. Эдакий Write once – translate to anything.
Double Selection Sort на cito:
{
public static int[] sort(int[]# numbers, int length)
{
int[]# sortedNumbers = new int[length];
for (int i = 0; i < length; i++) {
sortedNumbers[i] = numbers[i];
}
for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
int minimalNumberIndex = leftCursor;
int minimalNumber = sortedNumbers[leftCursor];
int rightCursor = length - (leftCursor + 1);
int maximalNumberIndex = rightCursor;
int maximalNumber = sortedNumbers[maximalNumberIndex];
for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
minimalNumber = cursorNumber;
minimalNumberIndex = cursor;
}
if (maximalNumber < cursorNumber) {
maximalNumber = cursorNumber;
maximalNumberIndex = cursor;
}
}
if (leftCursor == maximalNumberIndex) {
maximalNumberIndex = minimalNumberIndex;
}
int fromNumber = sortedNumbers[leftCursor];
int toNumber = sortedNumbers[minimalNumberIndex];
sortedNumbers[minimalNumberIndex] = fromNumber;
sortedNumbers[leftCursor] = toNumber;
fromNumber = sortedNumbers[rightCursor];
toNumber = sortedNumbers[maximalNumberIndex];
sortedNumbers[maximalNumberIndex] = fromNumber;
sortedNumbers[rightCursor] = toNumber;
}
return sortedNumbers;
}
}
Links
https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito
Quellen
https://www.researchgate.net/publication/330084245_Improved_Double_Selection_Sort_using_Algorithm
http://algolab.valemak.com/selection-double
https://www.geeksforgeeks.org/sorting-algorithm-slightly-improves-selection-sort/
