What are the odds?

How unlikely is unlikely?

A while ago I saw a video of a sorting algorithm visualizer. It made sounds and everything! It … scratched my brain. Like an itch I did not know I had. So I decided to make my own. Make it nice, add some colors, some sounds and a bunch of different algorithms.

Implementation

I decided to go with an array of 52 numbers, 1 - 52. It just looks good. Also its a nice challenge for the algorithms so there is a bit of time to visualize the sorting. Setting up the sorting was pretty annoying. The math for the different algorithms is available online and easy enough to make your own version of. I wrote this originally in javascript with types using jsdoc comments… then I realized I was doing types without out the niceties of typescript with worse looking code. So I ended up doing a rewrite in typescript eventually.

The we shuffle the array send it over to the selected array and let it do its thing. Each algorithm produces an async promise that delivers the state of the array until it is sorted. Pretty simple. Had some minor issues with some of the algorithms (the ones that split the array) not being correctly sorted, getting the damn bars to scale to the display width and many issues with getting the audio of the sorting process not to sound like you were torturing an alien. But after a while the project was looking pretty solid. I could now look at, and hear, algorithms sort through pillars of different heights. The marvels of the modern age never seas to amaze. Flying cars be damned.

After setting this up I was sitting and staring at my different sorting algorithms go. The amazing inefficiency of buble-sort, the mesmerizing back and forth of cocktail-sort, the structure of heap-sort and the efficiency of quick-sort, I started wondering about the maths of this.

Maths

An array of 52 items. There are 52! possible combinations … witch is a rather large number. 8.07 × 10^67, same number as a deck of cards. And as they say, if you shuffle a deck it will in all likelihood be a combination of those cards that has never been in that exact order before.

To paint the picture more dramatically, there are about 1.3 × 10^57 atoms in our solar system, 52! is around 62 billion times larger. So if you were to shuffle a deck of cards every second since the big bang, you would still not have shuffled through all the combinations.

The number of combinations being so large is just when we are looking at the ods of every item being in the right place. Most of the sorting algorithms are just doing basic comparisons and swaps on items next to each other, so sorting the array does not take that long. Even buble-sort, with no delay set, does it in around 6 seconds. Quick-sort does it in a little over a second. The bottleneck is the visualization and sound. This visualizer is not made for speed but for showing how the different algorithms work. And since they all run with the same array size and parameters, the speed difference should still be representative of the different algorithms.

Bogo-sort

When I was looking at the bars get sorted I switched to bogo-sort. The meme of an algorithm, shuffling the array, checking if it is sorted, if not shuffle again. Rinse and repeat until sorted. The odds of bogo-sort working with this size of an array are so insane that it is not even funny. The expected number of shuffles to sort an array of 52 items is 52! (8.07 × 10^67). If you could do a shuffle every nanosecond it would take you around 2.56 × 10^51 years to sort the array. The universe is estimated to be around 1.38 × 10^10 years old. So you would need to wait around 1.85 × 10^41 times the age of the universe to get a sorted array with bogo-sort. Or it could just work on the first try. But the odds, like I have laid out, are not in your favor.

Humans and probability

Humans are really bad at understanding probability. We tend to see patterns where there are none, we think that a coin that has landed on heads 5 times in a row is more likely to land on tails the next time (it is not, the odds are still 50/50). We also tend to underestimate the odds of very unlikely events happening. Like winning the lottery. The odds of winning the jackpot in a 6/49 lottery are around 1 in 13.98 million. Yet people buy tickets all the time, thinking they might win. The reality is that you are more likely to be struck by lightning (1 in 1.2 million) than to win the lottery. There is a known myth that if you strike your palm against a table there is a tiny, miniscule, infinitesimally small chance that the atoms in your hand will all line up wit the tables and you will phase through the table. The odds of this happening are around 1 in 10^24. So while it is technically possible, it is so unlikely that it is not worth considering… but that does not stop teens around the world smacking their tables every now and again, because hey, you never know.

We love to think that odds are stupid and for us they do not apply or that its different for us.

I think it is our nature to see hope, even when the odds are against us. We want to believe that the impossible is possible, or at least that the unlikely is not really that unlikely.

I even created an intelligent bogo-sort that saves each permutation it has tried and does not try it again. This costs memory, I was hoping to write something that was a bit of a memory leak, but storing different permutations of 52 items does not take that much memory. I ran it for 10 minutes and it had only used around 200mb. Burns through my battery like crazy though.

Maybe one day

The highest I have ever seen the intBogo-sort get is 15%. I run it every now and again, hoping to see it get a bit further. Maybe one day I will run the sort and it will instantly sort the array, one day. And on that day I will stand on a hill with a long metal rod, during a lighting storm, slapping my palm against a table, while winning the lottery. Because hey, you never know.

You can run the visualizer yourself here.