Title: Add Optimized Permutation/Deterministic BogoSort (aka Optimized Smart BogoSort) by wakfi · Pull Request #2 · aphitorite/ArrayVisualizer · GitHub
Open Graph Title: Add Optimized Permutation/Deterministic BogoSort (aka Optimized Smart BogoSort) by wakfi · Pull Request #2 · aphitorite/ArrayVisualizer
X Title: Add Optimized Permutation/Deterministic BogoSort (aka Optimized Smart BogoSort) by wakfi · Pull Request #2 · aphitorite/ArrayVisualizer
Description: Deterministic Bogosort, based on permutations, can be done with no wasted operations; every single swap creates a new permutation that has not occurred yet, no overlaps with any previous states of the array. This is accomplished using Heap's Algorithm applied with checks for sort. This is the most efficient strategy for a permutation sort. The only caveat is that I have implemented it using recursion; I've considered trying it without recursion but I feel it would add more writes and comparisons than it would save memory, especially since bogosort gets ridiculously long so quickly that the function call stack won't be able to get large enough to matter. I've done some performance checks between SmartBogoSort and this implementation (by adding 10 and 12 to the array sizes to get better benchmarks) to verify that it is actually an optimization, and confirmed that it is considerably faster and uses less operations. The maximum amount of swaps this implementation will do given a worst case input is exactly n!; the number of comparisons appears to be between 3-5 times the number of swaps in general. I'm pulling against this branch as this is the branch that MusicTheorist#14 is open from, and I thought it would make the most sense to add it to the existing pull request; I also wanted to submit it to your consideration as you already have an implementation of the same concept awaiting approval.
Open Graph Description: Deterministic Bogosort, based on permutations, can be done with no wasted operations; every single swap creates a new permutation that has not occurred yet, no overlaps with any previous states of ...
X Description: Deterministic Bogosort, based on permutations, can be done with no wasted operations; every single swap creates a new permutation that has not occurred yet, no overlaps with any previous states of ...
Opengraph URL: https://github.com/aphitorite/ArrayVisualizer/pull/2
X: @github
Domain: patch-diff.githubusercontent.com
| route-pattern | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:be4d058b-debf-ced7-5f9f-916183e6140e |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | E0E4:60AD3:FB6E3:158A0C:698DEE8D |
| html-safe-nonce | 74aca832451df5717b671295fe35050925ca7855f3b60585fb43afe8e42ebc9e |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJFMEU0OjYwQUQzOkZCNkUzOjE1OEEwQzo2OThERUU4RCIsInZpc2l0b3JfaWQiOiI0NjE4MDMwNzA0ODAxNzM4MzgxIiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0= |
| visitor-hmac | fe84e5cfe9b7d182eb34fb1b7e948005d12be0105ea01de20872bafe4f9b2847 |
| hovercard-subject-tag | pull_request:467816014 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/aphitorite/ArrayVisualizer/pull/2/files |
| twitter:image | https://avatars.githubusercontent.com/u/55608093?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/55608093?s=400&v=4 |
| og:image:alt | Deterministic Bogosort, based on permutations, can be done with no wasted operations; every single swap creates a new permutation that has not occurred yet, no overlaps with any previous states of ... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 929d0ce8b653d60df0698366d7e9012f9423ea1bace40816e16e5b007242aae4 |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/aphitorite/ArrayVisualizer git https://github.com/aphitorite/ArrayVisualizer.git |
| octolytics-dimension-user_id | 66573194 |
| octolytics-dimension-user_login | aphitorite |
| octolytics-dimension-repository_id | 270458119 |
| octolytics-dimension-repository_nwo | aphitorite/ArrayVisualizer |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | true |
| octolytics-dimension-repository_parent_id | 189810883 |
| octolytics-dimension-repository_parent_nwo | MusicTheorist/ArrayVisualizer |
| octolytics-dimension-repository_network_root_id | 19898492 |
| octolytics-dimension-repository_network_root_nwo | w0rthy/ArrayVisualizer |
| turbo-body-classes | logged-out env-production page-responsive full-width |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 143e58641f5eb460a02eda3a18cc1ef28e8c5188 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
Viewport: width=device-width