double section sort Archives

Double Selection Sort – 選択ソートのサブタイプで、速度が 2 倍になるようです。バニラのアルゴリズムは、数値のリストを 2 回ループし、最小の数値を見つけて、上のレベルのループが指す現在の数値と位置を交換します。二重選択ソートでは、最小値と最大値を検索し、– より上のレベルでループが指す 2 桁を置き換えます。左右に 2 つの数字。この乱交全体は、置換される数字のカーソルがリストの中央に見つかると終了します。その結果、ソートされた数字が視覚的中心の左右に取得されます。
アルゴリズムの時間計算量は、選択ソートと同様です。 O(n²) ですが、おそらく 30 の加速度があると思われます%。

境界線の状態

この段階ですでに、衝突の瞬間を想像することができます。たとえば、左カーソルの番号 (最小値) がリスト内の最大値を指しているとき、最小値が再配置され、再配置が行われます。最大数がすぐに壊れてしまいます。したがって、アルゴリズムのすべての実装には、そのようなケースのチェックとインデックスの正しいものへの置き換えが含まれます。私の実装では、1 回のチェックで十分でした。

  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;
    }
}

リンク

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/doubleSelectionSort
https://github.com/pfusik/cito

ソース

https://www.researchgate.net/publication/330084245_改良_Double_Selection_Sort_using_Algorithm
http://algolab.valemak.com/selection-double
https://www.geeksforgeeks.org/sorting-algorithm-slightly-improves-selection-sort/