Classificação por seleção dupla – um subtipo de classificação por seleção, parece que deveria ser duas vezes mais rápido. O algoritmo vanilla faz um loop duplo pela lista de números, encontra o número mínimo e troca de lugar com o número atual apontado pelo loop no nível acima. A classificação por seleção dupla procura os números mínimo e máximo e, em seguida, substitui os dois dígitos apontados pelo loop no nível acima de – dois números à esquerda e à direita. Toda essa orgia termina quando os cursores dos números a serem substituídos são encontrados no meio da lista e, como resultado, os números ordenados são obtidos à esquerda e à direita do centro visual.
A complexidade de tempo do algoritmo é semelhante à classificação por seleção – O(n2), mas supostamente há uma aceleração de 30 %.
Estado limítrofe
Já nesta fase, você pode imaginar o momento de uma colisão, por exemplo, quando o número do cursor esquerdo (o número mínimo) aponta para o número máximo da lista, então o número mínimo é reorganizado, o rearranjo do número máximo quebra imediatamente. Portanto, todas as implementações do algoritmo contêm a verificação de tais casos e a substituição dos índices pelos corretos. Na minha implementação, uma verificação foi suficiente:
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 /algoritmos/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito
Fontes
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/
