{"id":3158,"date":"2022-06-25T22:54:57","date_gmt":"2022-06-25T19:54:57","guid":{"rendered":"https:\/\/demensdeum.com\/blog\/?p=3158"},"modified":"2024-12-16T22:32:19","modified_gmt":"2024-12-16T19:32:19","slug":"bogosort","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/de\/2022\/06\/25\/bogosort\/","title":{"rendered":"Bogosort"},"content":{"rendered":"

Pseudosortierung oder Sumpfsortierung, einer der nutzlosesten Sortieralgorithmen.<\/p>\n

Es funktioniert so:
1. Die Eingabe ist ein Array von Zahlen
2. Eine Reihe von Zahlen wird zuf\u00e4llig gemischt (shuffle)
3. Pr\u00fcft, ob das Array sortiert ist
4. Wenn nicht sortiert, wird das Array erneut gemischt
5. All diese Aktionen werden wiederholt, bis das Array zuf\u00e4llig sortiert ist.<\/p>\n

Wie Sie sehen k\u00f6nnen, ist die Leistung dieses Algorithmus schrecklich. Kluge Leute glauben, dass sogar O(n * n!) d. h. Es besteht die M\u00f6glichkeit, dass Sie viele Jahre lang beim W\u00fcrfeln zum Ruhm des Gottes des Chaos stecken bleiben. Das Array wird nie sortiert, oder vielleicht wird es sortiert?<\/em><\/strong ><\/p>\n

Implementierung<\/h3>\n

Um es in TypeScript zu implementieren, musste ich die folgenden Funktionen implementieren:
1. Mischen Sie ein Array von Objekten
2. Array-Vergleich
3. Generieren einer Zufallszahl im Bereich von Null bis zu einer Zahl (sic!)
4. Druckfortschritt, weil es scheint, dass das Sortieren endlos weitergeht<\/p>\n

Unten finden Sie den TypeScript-Implementierungscode:<\/p>\n

\n
const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);\nconst isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);\nconst shuffle = (array: any[]) => {\n    for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); var temp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));\nconst originalNumbers = [...numbers];\nconst sortedNumbers = [...numbers].sort();\n\nlet numberOfRuns = 1;\n\ndo {\n    if (numberOfRuns % 1000 == 0) {\n        printoutProcess(originalNumbers, numbers, numberOfRuns);\n    }\n    shuffle(numbers);\n    numberOfRuns++;\n} while (isEqual(numbers, sortedNumbers) == false)\n\nconsole.log(`Success!`);\nconsole.log(`Run number: ${numberOfRuns}`)\nconsole.log(`Original numbers: ${originalNumbers}`);\nconsole.log(`Current numbers: ${originalNumbers}`);\nconsole.log(`Sorted numbers: ${sortedNumbers}`);<\/code><\/pre>\n
\u0414\u043b\u044f \u043e\u0442\u043b\u0430\u0434\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c VSCode \u0438 \u043f\u043b\u0430\u0433\u0438\u043d TypeScript Debugger \u043e\u0442 kakumei.<\/p>\n
\u041a\u0430\u043a \u0434\u043e\u043b\u0433\u043e<\/h3>\n
\u0412\u044b\u0432\u043e\u0434 \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430:<\/p>\n
\n
src\/bogosort.ts:1\nStill trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000\nsrc\/bogosort.ts:2\nStill trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000\nsrc\/bogosort.ts:2\nStill trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000\nsrc\/bogosort.ts:2\nStill trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000\nsrc\/bogosort.ts:2\nSuccess!\nsrc\/bogosort.ts:24\nRun number: 148798\nsrc\/bogosort.ts:25\nOriginal numbers: 5,4,8,7,5,0,2,9,7,2\nsrc\/bogosort.ts:26\nCurrent numbers: 5,4,8,7,5,0,2,9,7,2\nsrc\/bogosort.ts:27\nSorted numbers: 0,2,2,4,5,5,7,7,8,9<\/code><\/pre>\n
\u0414\u043b\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0438\u0437 10 \u0447\u0438\u0441\u0435\u043b \u0411\u043e\u0433\u043e\u0441\u043e\u0440\u0442 \u043f\u0435\u0440\u0435\u043c\u0435\u0448\u0438\u0432\u0430\u043b \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 148798 \u0440\u0430\u0437, \u043c\u043d\u043e\u0433\u043e\u0432\u0430\u0442\u043e \u0434\u0430?<\/strong><\/em>
\n\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u043a \u0443\u0447\u0435\u0431\u043d\u044b\u0439, \u0434\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0435\u0439 \u044f\u0437\u044b\u043a\u0430 \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u043e\u0438\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043d\u0430 \u0440\u044b\u043d\u043a\u0435. \u041b\u0438\u0447\u043d\u043e \u044f \u0431\u044b\u043b \u0443\u0434\u0438\u0432\u043b\u0435\u043d \u0443\u0437\u043d\u0430\u0432 \u0447\u0442\u043e \u0432 \u0432\u0430\u043d\u0438\u043b\u044c\u043d\u044b\u0445 JS \u0438 TS \u0434\u043e \u0441\u0438\u0445 \u043f\u043e\u0440 \u043d\u0435\u0442 \u0441\u0432\u043e\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u0448\u0438\u0432\u0430\u043d\u0438\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432, \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u0446\u0435\u043b\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0432 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0435, \u0434\u043e\u0441\u0442\u0443\u043f\u0430 \u043a \u0445\u044d\u0448\u0430\u043c \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0434\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f.<\/p>\n
\u0421\u0441\u044b\u043b\u043a\u0438<\/h3>\n
https:\/\/gitlab.com\/demensdeum\/algorithms\/-\/tree\/master\/sortAlgorithms\/bogosort<\/a>
\nhttps:\/\/www.typescriptlang.org\/<\/a>
\nhttps:\/\/marketplace.visualstudio.com\/items?itemName=kakumei.ts-debug<\/a><\/p>\n
\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438<\/h3>\n
https:\/\/www.youtube.com\/watch?v=r2N3scbd_jg<\/a>
\nhttps:\/\/en.wikipedia.org\/wiki\/Bogosort<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Pseudosortierung oder Sumpfsortierung, einer der nutzlosesten Sortieralgorithmen. Es funktioniert so:1. Die Eingabe ist ein Array von Zahlen2. Eine Reihe von Zahlen wird zuf\u00e4llig gemischt (shuffle)3. Pr\u00fcft, ob das Array sortiert ist4. Wenn nicht sortiert, wird das Array erneut gemischt5. All diese Aktionen werden wiederholt, bis das Array zuf\u00e4llig sortiert ist. Wie Sie sehen k\u00f6nnen, istContinue reading “Bogosort”<\/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,189,190],"class_list":["post-3158","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-bogosort","tag-sorting","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"de","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"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},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3158","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/comments?post=3158"}],"version-history":[{"count":15,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3158\/revisions"}],"predecessor-version":[{"id":3881,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3158\/revisions\/3881"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/media?parent=3158"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/categories?post=3158"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/tags?post=3158"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}