Counting Sort

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
  • 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(R) Xeon(R) 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

 

Advertisements

One thought on “Counting Sort

  1. Pingback: Heap Sort vs Merge Sort vs Insertion Sort vs Radix Sort vs Counting Sort vs Quick Sort |

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s