Thread: Counting Sorting Algorithm

We were recently given a problem in class that I had no idea how to start on. If anybody could give me some guidance on how to start that would be great!

The goal of the exercise is to experiment with the performance degradation caused by high rate of cache misses. To this end, you are required to implement a well-known algorithm for sorting integer numbers and try it on larger and larger input data sets.
This algorithm is the counting sort algorithm. At its wikipedia page, you will find a detailed description of this algorithm.

• 1. Realize a C Program implementing the counting sort algorithm. The input of this program is simply two positive integers n and k. The integer n is the size of the array to be sorted. The entries of this array are random non-negative integers less or equal than k. There will be no output for this program, since we are only interested in its running time.
• 2. Set k to be the largest value of a C int. Measure the running time for n = i * 100000000 where i is successively 1,2,3,4,5,6.
• 3. Theoretically, the number of operations performed by the counting sort algorithm is (asymptotically) proportional to n + k. Do the experimental results of the previous question reflect that fact? If not, explain why. Hint: Try to estimate the number of caches incured by the algorithm when both n and k are larger than the size of the L1 cache.

Welcome to the forum, neilman!

You will need a program that:

Can measure the running time of the program: so include time.h in your #include file

Can tell your program, what your INT_MAX value is, for your compiler (yes, it varies a great deal). To get that value, you should include the limits.h file

The counting sort code itself, which is very little, - two lines of code.

Have you read the Wikipedia page on counting sort yet?

Here's what you need to do. Get started with the program, and see how it goes, OK. When and if you get stuck, post up your code (or at least the part you're having trouble with), so we can see it, and tell us what the problem is. The more specific you are, the easier it is to help.

The start of the program is entirely up to you - we will not start the program for you. This is not as tough an assignment as it sounds.

Originally Posted by iMalc

What can you do?
Can you create an empty "hello world" program and run it? If not, start there.
Can you parse input from the command line? If so, do that next, otherwise just use hard-coded values for now.
Can you create an array and fill it with random values? If not, perhaps have a go at that anyway.

Post some code!

I can do the hello world program,, but I am unsure about what the other two mean? I have been reading this website for hours today and still cannot make heads or tails of this question.