Is bogosort really all that bad?

Big-O is important

Except for when it's not.

I've seen a lot of people - not just developers but actual, real-life people, waste so much effort on micro optimizations at the expense of macro disadvantages.

That's not to say that you shouldn't have the good common sense to avoid O(n^2) when your real problem is more along the lines of O(2n), but there's no sense in going back to fix an O(n^2) in a list of root level navigation tabs on a website.

(Conversely I often have wondered why the gmail app takes whole seconds to search through a list of just a few thousand contacts on my phone - and Firefox OS has the same problem)

So how terrible is bogosort?

For the sake of argument / curiosity / fun (take your pick): At what number of elements does bogosort become "too slow"?

Let's define "slow" as "I could blink and not miss it" - roughly 300ms - and "too slow" as "I started thinking about / doing something else" - roughly 650ms.

Note: For those of you not in the know, bogosort is an "algorithm" for sorting lists - like putting numbers in order. The way the algorithm works is that it shuffles all of the items randomly and then checks to see if they're in the right order or not - meaning it would fail and try again if any preceding number is greater than its successor.

So here's our bogosort test:

After running it a few times, here's some of the result sets I get:

Number of items	Time (ms)
1	0
2	0
3	0
4	0
5	1
6	1
7	69
8	39
9	410
10	30547

Number of items	Time (ms)
1	0
2	0
3	0
4	0
5	0
6	1
7	10
8	361
9	1725

Update

For comparison I used a better randomize algorithm (fisher-yates/knuth shuffle) and I was not surprised to see that it was an order of magnitude faster on average - even though and I'm fairly sure it's more computationally intensive.

Check out the optimized bogosort.

Here are some samples:

List Size	Milliseconds
1	0
2	0
3	0
4	0
5	1
6	1
7	0
8	7
9	149
10	754

List Size	Milliseconds
1	0
2	0
3	0
4	0
5	1
6	0
7	5
8	5
9	180
10	383
10	17796

Using process.hrtime()

List Size	Seconds
1	0.000178629
2	0.000037074
3	0.000005097
4	0.000009899
5	0.000445547
6	0.000263364
7	0.004096409
8	0.004580194
9	0.150200741
10	0.793862271
11	18.020675493

And, of course, with v8's jit optimizer kicking in after a few thousand loops, it starts to get a little faster before it gets much much slower. :D

Conclusions

Use fisher-yates/knuth shuffle, (see visual explanation) because if you use Math.random(), you'll get sued a la Microsoft MSIE ballot

If you had a personal blog and wanted to use it to sort your top-level navigation bar, it would probably do just fine.

If however, you wanted to sort your blog posts by date (or whatever), I'd have to recommend a different algorithm.

note: it would be interesting to see the number in terms of clock cycles or nano seconds or something where the scale is more apparent. I wouldn't be surprised if the reality of the jump is that by the time we get to 13 it takes hours. done!

rainy day todo: run the test 100 times and report the averages

Conclusion-ception: Writing this article, and especially coming back to update it with an optimized bogosort, is a perfect example of micro advantages as the expense of macro disadvantages.

By AJ ONeal


Did I make your day?
Buy me a coffee  

(you can learn about the bigger picture I'm working towards on my patreon page )

---

---