Sorting Algorithms

I suspected that a hybrid of a stooge and a bogosort would be quicker than a straight bogosort. Turns out I was right.

Hybrid Stooge-Bogo sort

  1. Bogosort the first 2/3 of the list
  2. Bogosort the last 2/3 of the list
  3. Bogosort the first 2/3 of the list

Turns out though, that the bogosort is quicker in cases where the list is already sorted since it does fewer “is it sorted” checks before exiting.

A straight stooge sort is usually quicker than the stooge-bogo hybrid though.

There. Isn’t that useful information?

Pitting Stooge Sort, Bogo Sort and Hybrid bogo-stooge sorting against each other:

For length 1 Bogo wins.(stooge : 0.000003, Hybrid: 0.000062 Bogo: 0.000002)
For length 2 Stooge wins.(stooge : 0.000003, Hybrid: 0.000020 Bogo: 0.000467)
For length 3 Stooge wins.(stooge : 0.000028, Hybrid: 0.000177 Bogo: 0.000169)
For length 4 Stooge wins.(stooge : 0.000074, Hybrid: 0.001401 Bogo: 0.004980)
For length 5 Stooge wins.(stooge : 0.000110, Hybrid: 0.005993 Bogo: 0.013229)
For length 6 Stooge wins.(stooge : 0.000151, Hybrid: 0.002046 Bogo: 0.039309)
For length 7 Stooge wins.(stooge : 0.000272, Hybrid: 0.038909 Bogo: 0.125351)
For length 8 Stooge wins.(stooge : 0.000253, Hybrid: 0.095385 Bogo: 0.777875)
For length 9 Stooge wins.(stooge : 0.000410, Hybrid: 0.246479 Bogo: 19.195493)

To be interesting and add Bozosort to the list instead of Stooge sort:

For length 1 Bogo wins.(bozo : 0.000004, Hybrid: 0.000017 Bogo: 0.000002)
For length 2 Bogo wins.(bozo : 0.000020, Hybrid: 0.000020 Bogo: 0.000002)
For length 3 Bogo wins.(bozo : 0.000034, Hybrid: 0.001125 Bogo: 0.000031)
For length 4 Bozo wins.(bozo : 0.000117, Hybrid: 0.001645 Bogo: 0.004542)
For length 5 Bozo wins.(bozo : 0.000231, Hybrid: 0.010748 Bogo: 0.009622)
For length 6 Bozo wins.(bozo : 0.004700, Hybrid: 0.006521 Bogo: 0.022846)
For length 7 Hybrid wins. (bozo : 0.072314, Hybrid: 0.038041 Bogo: 0.144553)
For length 8 Hybrid wins. (bozo : 0.242777, Hybrid: 0.108764 Bogo: 23.163011)
For length 9 Hybrid wins. (bozo : 3.688617, Hybrid: 0.221937 Bogo: 2.503227)

This wasn’t strictly a fair test, since each of the times listed for a given length is actually a different list, but it should give some idea. Testing after each swap (bozosort) seems to beat testing after many swaps (bogosort) in some cases.

Most useless app ever? Not quite…

I was playing around with XCode and came up with this simple counter:

(Almost) The most useless app ever
(Almost) The most useless app ever

You hit the count button and it counts. That is all.

If you’re crazy enough to want to try it, here it is: Counter 1.0.dmg
It’s built on Mountain Lion, so I very much doubt it’ll work on anything else.

Why did I do this? Because I wanted to play with some Cocoa objective C and lacked any other ideas.

Big day for the internet (A.K.A Digg dugg it’s own grave)

Dig was sold today yesterday for $500,000. This was bound to happen eventually – it has been a shell of it’s former self for a while now. What interests me though isn’t that it was sold, it was the events leading up to it.

I started using Digg on the 2nd March 2006 when I discovered it through a now long gone forum as it was being used to generate an RSS feed for the news section. I used it for a while, then eventually started watching diggnation (I stopped watching this about 18 months before it ended for various reasons – but that deserves it’s own post) I tended to use it to catch those stories on mainstream news sites that I may have missed. I was never interested in the obscure blogs or viral videos for the most part. I liked the top diggs list, rarely venturing into the “upcoming” section because it contained too much unfiltered crap.

This leads me nicely to why I don’t use reddit. Firstly, since I was using digg from a little while before it really peaked, I prefered the original and at the time best. Reddit is essentially a bad clone of digg. The UI is horrible,and the stories are (or at least at the time were) more viral content than actual news. Nowadays I like Google news (usually on my android) to fill this need.

As much as Facebook and Twitter can be blamed partially for Digg’s downfall, in my mind the real killer was the “V4” redesign. Oddly, I didn’t know what the uproar was about when it was launched, but looking back, as much as I tried to like it, the site just wasn’t as interesting and i drifted away. the real feature that killed it was the “my news” view – as in, the fact it had a separate timeline for each user generated by who they were following. Essentially it was like twitter had a one night stand with an RSS reader. This removed the whole central concept of Digg: the central news feed! As much as the technology was a problem when it first launched (based around a cassandra DB) I was actually quite interested by that, and I do not think it was the underlying problem. I accept that the backend needed to be redesigned to scale, and that the site was being gamed. The problem was the solution was to essentially redesign the whole product, leaving out the key thing that made it work! The old functionality could have been done on a new backend and crashed just as much and yet people would be happy because they had the same site functionality. Previous changes had added functionality, while this change replaced it.

Digg became overrun by “Breaking News”, engadget, and other RSS feeds. it was no longer user submitted content, but more like an RSS feeder and a blender combined. Each story had significantly fewer diggs, and so the most interesting stories did not bubble up to the top so easilly. I’m fairly certain this change was to make it easier to sell slots – as in, make users subscribe to content feeds, then charge the content feeds for the exposure. Problem was it was forced on users.

So about half of Digg’s users deserted them. Ironically, I just took a look at now and the site has much of the original functionality that it had before the big upgrade. But the damage is already done – the users do not return once they leave.