Counting Sort
Sep 11, 2012 · Commentscode sortingalgoc++
Counting Sort is an integer sorting algorithm. It is not very famous when somebody talks about sorting algorithms but it is great when sorting integers. In fact, many a times it may even beat other Sorting Algorithms. The highlight of Counting Sort is that it creates a bucket array (to keep track of frequency of numbers) whose size is the maximum element in the provided array.
We are looking to compare most of the sorting algorithms to find out which one performs better under different circumstances. One of the ways is to compare the complexity for each algorithm. The other way is to compare how well they perform based on the input they are all provided. I will post my code on Github but will start with Counting Sort here.
Here are some pointers about Counting Sort:
Linear sorting algo with O(n+k) when the elements range from 1 to k
- On
- On
It is really good when the numbers range from 1 to n which means the max between them is not going to be very high
How do we compare all Sorting Algorithms?
We are going to look at the following scenarios across all Sorting Algorithms:
10 numbers - Random + Sorted
1000 numbers (1K) - Random + Sorted
1,000,000 numbers (1M) - Random + Sorted
20000 iterations for each one of these scenarios
For good measure we will look at the average time required to sort 100 numbers in each one of these cases
This will allow us to compare all algorithms against each other by looking at the average times
It means we will be multiplying the results of 10 numbers by 10 (to get the “average” for 100 numbers) and also
Machine Setup
The setup of my machine is as follows:
| Hardware: x86_64 | Processor: 16 x Intel® Xeon® E5540 2.53 GHz | Compiler: gcc version 4.8.2 (GCC) | Redhat Version: Red Hat 5.3
The Source Code
I am trying to do this all together in a single place so that it is easy for anybody to pick up the code, either for their own testing or going through the Sorting Algos. All of the source code for this can be found here:
https://github.com/abhi1010/Algorithms
Numbers
Without further ado, let’s delve into the numbers for Counting Sorts. Here’s the result from the code:
| # of Items in Array | Time Taken | Average for 100 numbers | |
| Random | 10 | 0.022982 | 0.22982 |
| 1K | 1.21822 | 0.121822 | |
| 1M | 1823.85 | 0.182385 | |
| Sorted | 10 | 0.026815 | 0.26815 |
| 1K | 1.19146 | 0.119146 | |
| 1M | 1612.58 | 0.161258 |