{"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\/fr\/2022\/07\/23\/double-selection-sort\/","title":{"rendered":"Tri \u00e0 double s\u00e9lection"},"content":{"rendered":"

Tri par s\u00e9lection double\u00a0: un sous-type de tri par s\u00e9lection, il semble qu’il devrait \u00eatre deux fois plus rapide. L’algorithme Vanilla effectue une double boucle dans la liste des nombres, trouve le nombre minimum et \u00e9change les places avec le num\u00e9ro actuel point\u00e9 par la boucle au niveau sup\u00e9rieur. Le tri par double s\u00e9lection recherche les nombres minimum et maximum, puis remplace les deux chiffres point\u00e9s par la boucle au niveau sup\u00e9rieur \u00e0 – deux chiffres \u00e0 gauche et \u00e0 droite. Toute cette orgie se termine lorsque les curseurs des nombres \u00e0 remplacer se trouvent au milieu de la liste, et par cons\u00e9quent, des nombres tri\u00e9s sont obtenus \u00e0 gauche et \u00e0 droite du centre visuel.
La complexit\u00e9 temporelle de l’algorithme est similaire \u00e0 celle du tri par s\u00e9lection – O(n2<\/sup>)<\/span><\/span>, mais soi-disant il y a une acc\u00e9l\u00e9ration de 30 %.<\/p>\n

\u00c9tat limite<\/h3>\n

D\u00e9j\u00e0 \u00e0 ce stade, vous pouvez imaginer le moment d’une collision, par exemple, lorsque le num\u00e9ro du curseur gauche (le nombre minimum) pointe vers le nombre maximum dans la liste, alors le nombre minimum est r\u00e9organis\u00e9, le r\u00e9arrangement du nombre maximum tombe imm\u00e9diatement en panne. Par cons\u00e9quent, toutes les impl\u00e9mentations de l’algorithme contiennent la v\u00e9rification de tels cas et le remplacement des index par des index corrects. Dans mon impl\u00e9mentation, une seule v\u00e9rification suffisait\u00a0:<\/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
Liens<\/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":"
Tri par s\u00e9lection double\u00a0: un sous-type de tri par s\u00e9lection, il semble qu’il devrait \u00eatre deux fois plus rapide. L’algorithme Vanilla effectue une double boucle dans la liste des nombres, trouve le nombre minimum et \u00e9change les places avec le num\u00e9ro actuel point\u00e9 par la boucle au niveau sup\u00e9rieur. Le tri par double s\u00e9lection rechercheContinue reading “Tri \u00e0 double s\u00e9lection”<\/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":"fr","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\/fr\/wp-json\/wp\/v2\/posts\/3295","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=3295"}],"version-history":[{"count":22,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3295\/revisions"}],"predecessor-version":[{"id":3873,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3295\/revisions\/3873"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=3295"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=3295"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=3295"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}