{"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\/hi\/2022\/06\/25\/bogosort\/","title":{"rendered":"Bogosort"},"content":{"rendered":"

Pseudo-sort or swamp sort, one of the most useless sorting algorithms.<\/p>\n

It works like this:
1. An array of numbers is fed to the input
2. An array of numbers is shuffled randomly
3. Check if the array is sorted
4. If not sorted, the array is shuffled again
5. This whole process is repeated until the array is sorted randomly.<\/p>\n

As you can see, the performance of this algorithm is terrible, smart people think that even O(n * n!), i.e. there is a chance to get stuck throwing dice for the glory of the god of chaos for many years, the array will still not be sorted, or maybe it will be sorted?<\/em><\/strong><\/p>\n

Implementation<\/h3>\n

To implement it in TypeScript, I needed to implement the following functions:
1. Shuffling an array of objects
2. Comparison of arrays
3. Generate a random number in the range from zero to a number (sic!)
4. Print progress, because it seems like sorting is going on forever<\/p>\n

Below is the implementation code in TypeScript:<\/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":"
Pseudo-sort or swamp sort, one of the most useless sorting algorithms. It works like this:1. An array of numbers is fed to the input2. An array of numbers is shuffled randomly3. Check if the array is sorted4. If not sorted, the array is shuffled again5. This whole process is repeated until the array is sortedContinue 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":"hi","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\/hi\/wp-json\/wp\/v2\/posts\/3158","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/comments?post=3158"}],"version-history":[{"count":15,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts\/3158\/revisions"}],"predecessor-version":[{"id":3881,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/posts\/3158\/revisions\/3881"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/media?parent=3158"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/categories?post=3158"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/hi\/wp-json\/wp\/v2\/tags?post=3158"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}