Optimizing the JAVA QuickSort implementation – a real-world study

I recently found a report I wrote on JAVAs quicksort algorithm as part of the INDA course last year. I read it through and it’s actually pretty interesting stuff if you’re interested in how QuickSort works and how we can optimize the algorithm for specific data sets. So I figured I’d release this for anyone who is interested! I’ll gladly accept comments on the report, so don’t be a stranger!

The abstract below:

In this report, we examine four implementations of the famous sorting algorithm known as QuickSort – the optimized one included in the Java API, and three barebone versions that we write ourselves. We then put these algorithms against each other to see which one is faster in sorting arbitrary and sorted data. We discover that whilst the Java implementation is the best in some cases, it can also be easily outperformed if you know a lot about your information.

You can download the report below (421KB PDF)
Mirror 1
Mirror 2

Make any computer run faster – the cool way!

Just wait until I try a multiplication!

Many people are familiar with the fact that their computer becomes more sluggish and less responsive over time, but few people know that this is caused by quarks (a sort of microscopic dust) gathering in the internal pathways of the Central Processing Unit (CPU) of the computer as shown in the image below. What happens when you reinstall your operating system is that the pathways are cleared during the first cold boot after reinstallation. Luckily, new research has found that there is another way of clearing the pathways, one that will make your computer feel pretty much as fast when you started it the very first time. Keep reading for instructions.

Some of the pathways most prone to clogging
include the 4-channel DMA bus.

Let’s do it – the cool way
The original research made by the HCDE university in Washington shows that the dust-quarks are highly susceptible to cold temperatures and fall apart into smaller particles when exposed for a prolonged amount of time. You might have felt this effect if you have a laptop and brought it in from a cold day outside, but cold itself is not the answer. Due to the way that a modern-day CPU is placed into a socket, the pathways become exposed only when the processor is put upside-down, which is why you  might not have felt a tremendous difference – the computer has to be placed so that the CPU is pointing downwards.

Testing time!
I was very interested in trying this out – here are the instructions:

• Cover laptop in a plastic bag to avoid any moist from the freezer. (Optional, I had no problems without it)
• Put laptop or stationary computer upside-down in  the freezer. I tried it for twenty minutes and got a fantastic  speed improvement!

Result
I ran SuperPi both before and after, calculating pi to 1M decimals. The result:
Before: Calculation took 43 seconds
After: Calculation took 36 seconds

This is a fantastic increase (Seven seconds!) , and I urge you all to try this fantastic new find out! Go ahead and let me know how much you managed to improve in the comments!

In other news…
I’m gonna be making the “In other news” section a permanent addition to my posts. That’d be all, folks!

A final note…
In case you haven’t noticed yet, this was my April fool’s joke for 2009! Although putting your computer in the freezer for a few minutes probably won’t kill it, it won’t make it go very much faster either! Cheers everyone!