poor bogosort. I know that feeling of being the last person in class to be working on a test, and the teacher waiting solely on you, and the other students just want to go home for the day, and... ugh... bogosort if you need support im here man
That both is really interesting but also absolutely ridiculous. I mean on one hand it'd make sense considering how bogo sort works, but on the other hand the fact its time range is from 0 to infinity is bewildering.
Worst Case Scenario: If there are n items, then there will be n! (n factorial=1x2x3x4x...x(n-1)x n) permutations until he finds the correct one! If there are 170 items, then he will have more than 1.80x10^308 permutations
I like how the stooge sort bot is just looking around mindlessly while waiting for bogo sort to finish, but it's been established already that they have incredibly poor eyesight so he's not really seeing anything.
Bogosort was my first introduction to why time complexity really matters. With a small number of elements, it doesn't matter if you use bubble sort or quick sort or whatever, but you try a bogosort on just 15 elements and you might as well just sort them yourself lol.
Quantum bogosort is a hypothetical sorting algorithm based on bogosort, created as an in-joke among computer scientists. The algorithm generates a random permutation of its input using a quantum source of entropy, checks if the list is sorted, and, if it is not, destroys the universe. Assuming that the many-worlds interpretation holds, the use of this algorithm will result in at least one surviving universe where the input was successfully sorted in O(n) time.
Okay, so, A. This series has been incredibly I formative. Now I can enjoy those random recommendations of visualized sorts on a whole new level, since I actually know what some of them do. B. You absolute *madlad,* you could not have driven the point more perfectly home with bogosort. I saw Stooge win, watched for maybe three more minutes, and then it *properly* dawned on me how the math worked out. And then I checked the video length, and burst out laughing. Absolutely amazing. Keep doing what you're doing, I'm gonna go watch the rest of your vids.
@@loreleihillard5078 I don't know man, maybe 25 IS the minimum, simply because I'm including all "normal" people (meaning without mental disabilities) which means very dumb people are part of the equation.
with most other sorting algorithms, there is usually some way, some arrangement of items you can use to maximize swaps, such as giving Stooge Sort a list that's inverted. but Bogosort goes through the same motions regardless of what it's trying to sort, meaning every configuration is simultaneously the best, and worst case scenario
For those wondering: the probability of a given list of n items being sorted on a random shuffle is 1 in n!. As an example, the 6 item list had 6! = 720 combinations so the odds of a given shuffle being correct were 1 in 720. Thus, bogo had a slightly higher than 50% chance of being correct after 479 permutations. The formula for finding the odds of success after t trials given n items using bogo sort is (1 - 1/n!)^t. The average amount of excess comparisons would have been 3. So we have (3 * 479) + 5 comparisons for a slightly higher than 50% chance of success = 1442. The formula for the amount of comparisons for a probability p of success with n items using bogo sort is n/2 log_(1-1/n!) (p) + n - 1. This formula works generally: if you have a random chance C(n) of being correct on a given trial and need to check the list to see if you're correct, then the average amount of comparisons needed is given by n/2 log_(1-C(n)) (p) + n - 1.
At 7:30 you can see BOGO get a batch only 1 off from sorted. At 31 to 27 comparisons, you can tell BOGO is practically as good as Stooge. I don't know what the rest of the video is about but since the conclusion is obvious, I think I'll save myself the thirty minutes.
That introduction part literally looks just like a freaky dream I had when I was a really young child, with the blue gradient background and the weirdly moving humanoid characters.
everyone's talking about bogo sort but man i feel bad for bubble sort he was finally gonna win one but was left with confusion while waiting 2 minutes for stooge sort to finish and eventually win
Imagine being the animator. The person actually animated it so that the balls actually move to where they are supposed to be. That had to be an insane amount of work.
I just realized a way to optimize Stooge Sort. If we notice that sublist 2 is already sorted, by making no swaps, that means when we go back to sublist 1, we don't need to swap, as it didn't change. This should work, even if we made changes to sublist 1 ahead of time. Check 1. Is sorted? Sure move on. Check 2. Is sorted? Skip 1. Is not? Sort. Check 1.
Apparently, the second shuffling has n! possibilities, all of equal probability of 1/n!. In the other hand, the frist shuffling has n^n possibilities, which have different chances dwoending on which. Accepting that you can only shuffle with at least 2 objects, and n^n is always bigger than n! for 2 and above, the second shuffling makes the Bogo sorting way more efficient.
Little did you know, I have an even more inefficient method! I check them semi-randomly, forget what I’ve already checked, take a break, do the whole thing again, and then have someone else double check my work. Trump that robots! Human inefficiency at its finest! 💪🧠
not me checking the video and seeing im only 7 fucking minutes into the video and bogo sort is just chugging along for like 33 out of the nearly 41 minutes of this video just sorting, speaks to it's hilariously inefficient existence, that is unless you're a very lucky person
Bogosort was actually quite lucky here. Finishing after 345 tries only has a chance of 38%. I expected it to take a lot longer, considering the >50% is at 499 tries. And when being unlucky, there's a 10% chance that it could've taken more than 1657 tries... That would've taken around 2 hours and 36 minutes... >_>
udiprod:bogosort,YOURE FIRED bogosort:i will teach you a lesson. *sorts balls* 666 years later.... udiprod:OK OK I AM TIRED PLEASE I'M SORRY bogosort:ok.
Bogo sort 2.0 : Have him keep track of all permutation and keep sorting until he's 99.9% sure the balls are sorted completely randomly. Then complete the sort.
Bogo sort has a best case of O(n) and a worst case of O((n+1)!), where n is the number of items. Here n = 9, so in the best case it will take 9 runs on average. The worst case however is (n+1)!, the ! means factorial. Factorials are multiplying every number starting from the factorial and going down to 1. Eg 3! = 3 x 2 x 1 = 6. For (n+1)! we can solve using n = 9; (n+1)! = (9+1)! = 10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3,628,800, over 3.6 million runs. 605 might seem like a lot, but this was extremely lucky, and I dare say the 605th shuffle was intentionally made to be correct because the animator was losing their sanity working on this.
I'm definitely not the first one to think of this, but Stooge sort would be cut significantly if step 3 was skipped whenever step 2 resulted in no change. Just that one modification. It's such a redundant sort.
What about bogobogosort? Bogosort, but it randomly picks an arrangement of balls and scrambles them until it gets there. If that arrangement happened to be the correct one, we’re done. If not, do it again.
I like to think about stooge sort as a bubble sort that suffers from anxiety and is obsessed with the fear that the part of the list he already sorted is shuffled when he is not looking, so he is always double, triple or quadruple checking
That’s quite a reasonable assessment. As the sort deals with larger and larger arrays, the vast majority of comparisons done become entirely redundant because it had already sorted that area and hasn’t touched it since.
Quantum bogosort: Start with an unsorted array. Shuffle the elements randomly If it's solved, print the array. If it's unsolved, destroy the universe. All remaining universes will have had an instant sorting.
@@derekliu793 Isn't that the one which Randomizes like Bogo sort but instead of randomizing the whole thing, it randomizes one item at a time, and once the item is correct, it randomizes 2 items all until it reaches a point in randomizes items at a time?
@@drinks_mayoAnimating it is probably the easy part. There gets a point in a CGI animation crew's life where they can't hand craft the animation anymore and have to write some custom animation software code that can do the incredibly detailed stuff, so the animators can take care of the bigger picture instead. This could have four or five sets of animations that could be chained and dynamically switched between. Then some code would actually calculate a sort and record every step, and the animation software would copy that recorded scenario. The animators would make the code look pretty, but the code would piece everything together. It would take little time to animate 1000 balls. They could make the rendering last until the end of the universe if they wanted to. And they wouldn't have to give any input for more than the first 30 seconds of the animation, and then the last 30 seconds of the animation. Also, there is no way you could pay anyone to animate this video. They probably did code something that would chain these animations together, regardless of the ball shuffle animation.
Stooge sort be like: "okay this is done, next one" "hmm, done" "wait lemme make sure its done" "seems done" "hold on is everything done" "looks like it" "ok next one" "hmm done"
Who will right Shakespeare's hamlet first? One human with really bad ocd double checking everything or a monkey on typewriter that restarts after every mistake
I hope they used something to automate the animation because I'm willing to bet at least 5 animators shot themselves before they even managed to convince someone to animate it.
However the difference between stooge and bogo is that if they are both fed with an already-sorted list, stooge will still waste your time, but not bogo
