double section sort – Demens Deum

Double Selection Sort – a subspecies of sorting by selection, it seems like it should be accelerated twice. The vanilla algorithm double loops through the list of numbers, finds the minimum number, and swaps it with the current digit pointed to by the loop at the level above. Double selection sort, on the other hand, looks for the minimum and maximum number, then it replaces the two digits indicated by the loop at the level above – two numbers on the left and on the right. All this orgy ends when the cursors of numbers to replace meet in the middle of the list, as a result, sorted numbers are obtained to the left and right of the visual center. The time complexity of the algorithm is similar to Selection Sort – O(n2), but supposedly there is a 30% speedup.

Corner case

Already at this stage, you can imagine the moment of collision, when the number of the left cursor (the minimum number) will point to the maximum number in the list, then the minimum number is permuted, the permutation of the maximum number immediately breaks down. Therefore, all implementations of the algorithm contain a check of such cases, replacement of indices with correct ones. In my implementation, one check was enough:

if (leftCursor == maximalNumberIndex) {
    maximalNumberIndex = minimalNumberIndex;
}

Cito implementation

Cito is a lib language, a translator language. You can write on it for C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, while knowing absolutely nothing about these languages. The source code in the Cito language is translated into the source code in the supported languages, then you can use it as a library, or directly by correcting the generated code by hand. A kind of Write once – translate to anything.
Double Selection Sort – Cito:

public class DoubleSelectionSort
{
    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

References

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/