Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort
I had written about sorting algorithms (Tag: Sorting) with details about what to look out for along with their code snippets but I wanted a do a quick comparison of all the algos together to see how do they perform when the same set of input is provided to them. Hence I started working on a simple implementation for each one of them. I have now put together all of them in a single project on GitHub. I ensured that they all have the same set of procedures during their run. Some of the items I wanted to ensure was:
-
Same input array
-
Same number of iterations. Each iteration having the same input
-
Each algo being timed the exact same way as another
Some of the algorithms being tested were:
How did we ensure Equality?
-
Created a simple base class for all algorithms:
AlgoStopwatch
* Responsible for benchmarking everything
* Provide a function called ``doSort()`` that would allow derived classes to implement their algorithm
* Ensures that every algorithm has a name and description - to help us distinguish
-
Another class to help manage the testing of all the algorithms:
AlgoDemo
* All instances are created here for the algorithms
* The input array is provided by this class to all algorithms
Code
As usual the code for the project is available here:
https://github.com/abhi1010/Algorithms
It can be run using Visual Studio without any changes.
Numbers
Looking at the numbers below, it may be hard to compare the actual values. Hence I decided to normalize them by calculating how much time will be required to sort 100 numbers using the same rate as the actual numbers. They are provided for all algorithms on the right-most column.