Sorting algorithms – the result!

I did a blog post last week that explained that I would be doing some tests to see how efficient sorting algorithms are. I have now done tests with a few sorting algorithms listed in the table above. If you would like to view the full results, I have a presentation here as well. If you would like my code for the bubble sort, quicksort, count sort or bogosort, download either of the two files below:

• Source code (Java)
• Compiled Java (JDK 1.6)

The end result of the study was that the Quicksort tends to be more efficient when used on larger data sets (because it does more comparison on smaller data sets), however the count sort is considerably more efficient, even though the version I wrote only supports positive integers.

The psychology of version numbers

I am not a psychologist and I don’t really claim to be any good at it. Yesterday Firefox 7 was released. The Firefox project changed its versioning system earlier this year so that know they will be doing regular updates increasing version numbers every few months – to the degree that this time last year I was using Firefox 3.6. Google Chrome works in a similar way – I’m currently using version 15 (beta) however this time last year I was using version 6 (final). Version 16 – ten versions later – is already available in the developer channel. But what is it about having big version numbers?

The first thing is that having a bigger number seems to convey age or maturity of a product. If I told you that I was 40 you would definitely assume that I was more mature than a 14 year old. If I told you that I’ve got an IQ of 160 you’d probably say I was highly intelligent*. Basically, the bigger the number, the better we assume it is.

Google Chrome using v14 current version suggests that it is more developed than Opera (v11), Internet Explorer (9), Firefox (7) and Safari(5?). People think that a new version number means that a lot more features. If this is the case, people will assume there are more features in Google Chrome.

Many people believe that Firefox increasing its release system is because they are trying to play catch-up firstly with the other browsers, but ultimately Google Chrome. Firefox is losing users dramatically, and Google Chrome is gaining them at the same rate (well, the same rate Firefox and Internet Explorer are losing them). I made a bet with a friend earlier this year that Google Chrome would overtake Firefox by 2012, and I still think it will – maybe even by November.

Firefox developers believe that increasing version numbers will increase inferred maturity or features. Whether it will or not, I don’t know. What I do know is that there are quite a lot of ads for Chrome on other browsers at the moment.

*Last time I did an IQ test I got this, but it was one of those dodgy online ones that is quite inaccurate.

Happy Birthday Google! (sort of)

Google is a teenager today. Or at least Google says it is. Which is a bit strange considering that the domain was registered on a September 15th and the company was incorporated on a 4th September. With a bit of research it doesn’t even appear that any of the founders have had anything significant happen to them on a September 27th. I think we all have to assume that this is Google, and if Google decided that the moon had a core of cheese, we might have to believe them.

Minor update to Treehouse Stampede cheater

If you read my blog yesterday you’ll know that I coded a simple application that lets you cheat at the Windows 8 sample application Treehouse Stampede by coming up with the five best possible words that will earn you the most points. I have coded a minor update to the cheater so that it will know allow you to set a maximum without recompiling the program by launching it as:

java wordCheat 10

Obviously, you would replace 10 with the maximum number of letters you would like to use. I’ve also now GPL’d the source code (and recompiled the program to match it). Here are the files you need to download:

• (Optional) Source code - only download if you want to mess around with it and change some settings
• English word list - just a small text file you’ll need to use otherwise the program will crash. It is an unmodified version of this word list.
• Java Executable - this is the actual executable. Navigate to the appropriate directory in CMD and then type “java wordCheat” (case is important) to start running it. To quit it just type the word exit instead of the three letters

I had considered writing a Metro app to fit along the side so that you could cheat that way, but I decided it would be cheating too much. I got my massive high score by having it run on another computer and getting someone else to type in the three letters and tell me the word.

Looking forward to the Doctor Who finale

I didn’t get a chance to blog about last night’s episode Closing Time but it was great. I was glad to see Craig back, but it was a shame the Amy and Rory didn’t feature that much. My favorite bit was the ending, where we see where the Doctor gets his hat and blue envelopes. The build up to the finale was far more important than the fact that the episode was relatively humorous and had Cybermen in. Something really important was getting to hear the rest of the song from Night Terrors although we already knew that the River kills the Doctor.

From the information we know I think it is probably safe to assume that this isn’t the end of the Doctor considering that Matt Smith is already signed up for next year’s series, which has also be commissioned. I would also be prepared to suggest that this will be River Song’s last episode because when we learnt that she ‘killed a good man’ she seemed sad as if that was genuinely what she believed had happened, which probably means that she won’t see the Doctor again.

As for what the question in is and who asks it, I genuinely don’t have a clue. But never mind. Overall, I think I’m looking forward to next week’s episode!

Cheating at Treehouse Stampede (Windows 8 sample app)

I’ve been playing around on Windows 8 for a few days now and I’ve had a look at the sample Metro apps it comes with – all developed by college interns at Microsoft over the summer. The apps are varied in quality but my favorite so far has to be a little word game called Treehouse Stampede. The idea behind the game is to protect yourself (in your treehouse) by spelling out words that use three given letters. For instance, if I were given the letters NTI I could spell the word interesting – and I’d probably get lots of points because it is quite long.

The game can be a bit of a nightmare when you can something like QZX, but I’ve found a very simple way of cheating (see my highscore!). I found a word list of English words on the internet and then wrote a very simple Java console application to load up the words. I then simply typed in the three letters I was given and it would identify the five best words for me to use within the limit set in the code:

This essentially makes the game incredibly easy, but it is still quite good fun. If you want to try this out yourself, just download the three files to the same directory:

• (Optional) Source code – only download if you want to mess around with it and change some settings
• English word list – just a small text file you’ll need to use
• Java Executable – this is the actual executable. Navigate to the appropriate directory in CMD and then type “java wordCheat” (case is important) to start running it. To quit it just type the word exit instead of the three letters

What went wrong at CERN?

The other day CERN announced that they had got some Neutrinos to travel faster than the Speed of Light. Normally when a discovery like this had been made the whole world would have jumped up with excitement because it is truly incredible. But they didn’t for the simple reason that no scientist on Earth has been able to explain it – which is a bit of a problem.

When Einstein wrote up his Special Theory of Relativity he stated that nothing can go faster than the Speed of Light. The Speed of Light is effectively the cosmic speed limit – nothing can go faster than it. The reason for this is to protect cause and effect, the cause must happen after the effect which is why we cannot travel faster, effectively, than time.The Speed of Light itself – 299,792,458 m/s is actually referring to the number of meters that light travels in a vacuum – i.e. space, rather than in air. Even meters (measurement) are based on the speed. Since 1905, nearly all physics has relied on the fact that nothing can go faster.

The best example I’ve heard of what will happen if something exceeded the Speed of Light is take a spacecraft that travels as close as possible to the speed of light. Say there are a group of people inside. If one of them gets up to go to the toilet, they are theoretically going faster than the speed of light – which has already been established as impossible. Therefore time has to slow itself down to ensure that the person cannot exceed the speed of light.

The problem that CERN have got is that they have got Neutrinos – sub-atomic electrically neutral things that are just above mass zero – to travel through some rock from Geneva to Italy. They had expected the particles to get there at the Speed of Light, but they were fractionally faster; they arrived 0.00000006 seconds earlier than expected – which didn’t really fit. Nothing should be able to go faster than the speed of light.

So CERN went back and checked their clocks when they did this. Nothing run. Checked all the equipment. Nothing wrong. Redid the experiment 16,000 times. Exactly the same result. So they published their results and basically asked the scientific community to find the mistake.

There are a lot of theories at to why this happened. The only thing I’ve thought of is that time slowed down relative to the particles, which sort of fits. Another popular theory is that there are extra dimensions within the universe that the particles were able to jump through to get to Italy faster. Ultimately, none of this really makes sense, but it is interesting all the same. Poor Einstein.

Chrome’s new New Tab page (v15 Beta)

When I went on Google Chrome Beta this morning I noticed a difference when I opened a new tab – it was newer. The folks at Google have updated the page (and blogged about it). Here is a quick screenshot of what it looks like:

The page now allows for flicking between Most Visited, Apps and Bookmarks – it has arrows on the left and right as well as a small menu at the bottom. I’m sure that the extra space where the titles had been has also now allowed for slightly bigger logos and the font has also changed. Judging by some of the comments on their launch post I would suggest that opinion is mixed of the new tab page and it is clear that it is buggy for some users, but I like it.

How quickly do you sort?

I was thinking about sorting algorithms earlier today and how efficient/inefficient they are. Some sort algorithms are incredibly slow and do actually take a significant amount of time, especially on slower computers. Sometimes, they are much faster. The standard sorting method for nearly all programming languages is the bubble sort because whilst it can be incredibly slow on very large amounts of data it will always get the right answer. Here is a nice animation from Wikipedia showing it working:

The algorithm is actually quite useful, however there are alternatives. Another incredibly common method is the shuffle sort, which is a variation of the bubble sort that effectively uses exactly the same method however does it in a different order. Some mathematicians and programmers think it is quicker than a bubble sort for most random list of numbers, however a friend and I found that it is actually a lot less efficient if the numbers are in complete reverse order with a few variations.

However, neither of these methods are as popular as the Quicksort algorithm which uses random numbers rather than structure to sort an array more quickly. By using random numbers it is able to target different areas at a time, meaning it can be more efficient for some arrays, and in a worst-case scenario it would be equally efficient as the bubble sort. Here is another nice animation from Wikipedia demonstrating how it works:

However, when the said friend and I were discussing sorting, it got me thinking. I started to wonder how speedy different sorting algorithms actually are, so I am going to do an investigation. The way this will work will be to have an array of the maximum length my computer can handle without crashing in C++ and for me to take some major sorting algorithms and add modifications in to record how many swaps (described in the above diagrams) take place and how many times the algorithm has to search through the array of random numbers. This will then allow me to evaluate the effectiveness of the different algorithms, and hopefully I’ll publish them on here!

Click here.

I don’t know how often I see the phrase ‘Click here’ when browsing the internet. I am sure that at least 90% of websites have it on 90% of their pages. It is probably one of the most used phrases on the internet. Click here, however, is actually a really bad phrase to use on the web. But why?

When Google (and other search engines that nobody actually uses) crawl through the internet they find links on the internet, and follow them. When they follow the links, they look where they are going and the text of the link. If a page is linked to with lots of similar phrases that appeared to be linked to the content of the page, it will appear better in search engine results. Using the text click here will therefore cause a page to be linked no higher, because the link is effectively useless to search engines.

The problem, of course, is that it is very difficult to think of a good way of adding a link into a sentence naturally. Unless you are using a very exact phrase like ‘Looking back at my review of blah, blah, blah‘ and linking everything from my, it can be incredibly difficult to get a link to be natural in text. A good way is to link sources however, like the Gawker blogs which have a link to a referenced article at the bottom of every post.

Ultimately, click here makes things difficult and it should really be avoided. Next time you go and type that in, please think.