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.

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!