{"id":3295,"date":"2022-07-23T14:25:24","date_gmt":"2022-07-23T11:25:24","guid":{"rendered":"https:\/\/demensdeum.com\/blog\/?p=3295"},"modified":"2024-12-16T22:32:18","modified_gmt":"2024-12-16T19:32:18","slug":"double-selection-sort","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/2022\/07\/23\/double-selection-sort\/","title":{"rendered":"Double Selection Sort"},"content":{"rendered":"

Double Selection Sort is a type of selection sort that should be twice as fast. The vanilla algorithm goes through a double loop over a 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 looks for the minimum and maximum number, then replaces the two digits pointed to by the loop at the level above – two numbers on the left and right. This whole orgy ends when the cursors of the numbers to be replaced 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<\/sup>)<\/span><\/span>, but there is supposedly a 30% speedup.<\/p>\n

Borderline state<\/h3>\n

Already at this stage, you can imagine the moment of collision, for example, when the number of the left cursor (minimum number) will point to the maximum number in the list, then the minimum number is rearranged, the maximum number rearrangement immediately breaks. Therefore, all implementations of the algorithm contain a check for such cases, replacing the indices with correct ones. In my implementation, one check was enough:<\/p>\n

\n
\n
  maximalNumberIndex = minimalNumberIndex;\n}<\/code><\/pre>\n<\/div>\n
\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043d\u0430 Cito<\/h3>\n
Cito \u2013 \u044f\u0437\u044b\u043a \u043b\u0438\u0431, \u044f\u0437\u044b\u043a \u0442\u0440\u0430\u043d\u0441\u043b\u044f\u0442\u043e\u0440. \u041d\u0430 \u043d\u0435\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u0438\u0441\u0430\u0442\u044c \u0434\u043b\u044f C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0437\u043d\u0430\u044f \u043f\u0440\u043e \u044d\u0442\u0438 \u044f\u0437\u044b\u043a\u0438. \u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Cito \u0442\u0440\u0430\u043d\u0441\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043a\u043e\u0434 \u043d\u0430 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u043c\u044b\u0445 \u044f\u0437\u044b\u043a\u0430\u0445, \u0434\u0430\u043b\u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u043a \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443, \u043b\u0438\u0431\u043e \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e, \u0438\u0441\u043f\u0440\u0430\u0432\u0438\u0432 \u0441\u0433\u0435\u043d\u0435\u0440\u0435\u043d\u043d\u044b\u0439 \u043a\u043e\u0434 \u0440\u0443\u043a\u0430\u043c\u0438. \u042d\u0434\u0430\u043a\u0438\u0439 Write once \u2013 translate to anything.
\nDouble Selection Sort \u043d\u0430 cito:<\/p>\n
\n
\n
{\n    public static int[] sort(int[]# numbers, int length)\n    {\n        int[]# sortedNumbers = new int[length];\n        for (int i = 0; i < length; i++) {\n            sortedNumbers[i] = numbers[i];\n        }\n        for (int leftCursor = 0; leftCursor < length \/ 2; leftCursor++) {\n            int minimalNumberIndex = leftCursor;\n            int minimalNumber = sortedNumbers[leftCursor];\n\n            int rightCursor = length - (leftCursor + 1);\n            int maximalNumberIndex = rightCursor;\n            int maximalNumber = sortedNumbers[maximalNumberIndex];\n\n            for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {\n                    minimalNumber = cursorNumber;\n                    minimalNumberIndex = cursor;\n                }\n                if (maximalNumber < cursorNumber) {\n                    maximalNumber = cursorNumber;\n                    maximalNumberIndex = cursor;\n                }\n            }\n\n            if (leftCursor == maximalNumberIndex) {\n                maximalNumberIndex = minimalNumberIndex;\n            }\n\n            int fromNumber = sortedNumbers[leftCursor];\n            int toNumber = sortedNumbers[minimalNumberIndex];\n            sortedNumbers[minimalNumberIndex] = fromNumber;\n            sortedNumbers[leftCursor] = toNumber;\n\n            fromNumber = sortedNumbers[rightCursor];\n            toNumber = sortedNumbers[maximalNumberIndex];\n            sortedNumbers[maximalNumberIndex] = fromNumber;\n            sortedNumbers[rightCursor] = toNumber;\n        }\n        return sortedNumbers;\n    }\n} \n<\/code><\/pre>\n<\/div>\n<\/div>\n
Links<\/h3>\n
https:\/\/gitlab.com\/demensdeum \/algorithms\/-\/tree\/master\/sortAlgorithms\/doubleSelectionSort<\/a>
https:\/\/github.com\/pfusik\/cito<\/a><\/p>\n
Sources<\/h3>\n
https:\/\/www.researchgate.net\/publication\/330084245_Improved_Double_Selection_Sort_using_Algorithm<\/a> 
http:\/\/algolab.valemak.com\/selection-double<\/a>
\nhttps:\/\/www.geeksforgeeks.org\/sorting-algorithm-slightly-improves-selection-sort\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Double Selection Sort is a type of selection sort that should be twice as fast. The vanilla algorithm goes through a double loop over a 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 looks for the minimumContinue reading “Double Selection Sort”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,196,190],"class_list":["post-3295","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-double-section-sort","tag-sorting","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"en","enabled_languages":["en","ru","zh","de","fr","ja","pt"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3295","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/comments?post=3295"}],"version-history":[{"count":22,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3295\/revisions"}],"predecessor-version":[{"id":3873,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3295\/revisions\/3873"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/media?parent=3295"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/categories?post=3295"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/tags?post=3295"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}