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

Pirates who pirate from pirates…

A few months ago I tried to code for the PSP in C, and whilst I never actually produced anything of interest it was a very interesting experience, and so I decided to try programming for the DS using DevKitPro. (And completely coincidentally also allow me to play one of the most unique rhythm games ever released.) So I went by my local store and purchased a DS, but besides the DS I also needed a “flashcart”, which allows for booting homebrew creations and game backups from a (usually) microSD card that is inserted into the cartridge. As I was checking out a few stores for possible choices I was dumbfounded by the ginormous (Yes it’s a word!) amount of different flash carts, and as I read more about them I was slightly amused about the entire business of flash carts for the DS. You see, the gist of it all is the following:

In order to allow booting of homebrew and backups, the flashcarts mimick the behaviour of a regular nintendo DS game and then execute an exploit in the dashboard to allow booting to it’s own custom kernel and menu, which then acts as a launcher for all of the media which is loaded onto the microSD card. Judging by the massive lawsuit that Nintendo and 54 other companies has brought upon the distributors of the R4 flashcart, they are not pleased with the development. Now the gist of the gist is that a particular flashcart is only as good as its kernel – good kernels play many backups and homebrew, and lesser kernels suffer from random crashes and bad compatibility. And what’s interesting is that while there are enough different flashcarts to take a bath in, there are only a handful of different kernels. Yes – many flashcart makers steal kernels, some by creating clones with a different name and firmware with a minimal set of differences (such as a new skin) and some by simply creating hardware which is compatible with the original company’s kernel. (An example of identification of a fake flash cart is shown below, courtesy of NDSTT.com)

Since these companies do not have to spend time and money on building a kernel, their flashcarts – while sometimes inferior in build quality are considerably cheaper than the originals, and guess what? The makers of the original flashcarts and kernels aren’t happy! Some have even gone to draconian methods such as threatening to include software that will permanently damage a fake card and accompanying memory card!

Seeing a pattern here?

I personally find it quite entertaining that people who basically condone to piracy are just as angry when their intellectual property is stepped on. What do you think? Leave a comment and let the world know!