Counting Sorting Algorithm

This is a discussion on Counting Sorting Algorithm within the C Programming forums, part of the General Programming Boards category; We were recently given a problem in class that I had no idea how to start on. If anybody could ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    2

    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.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    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!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Oct 2012
    Posts
    2
    Quote Originally Posted by iMalc View Post
    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.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Okay, start by making a program with an array in it. You have been taught arrays right?
    If you missed that class, then find a book or tutorial and read up about arrays.
    Maybe make a loop that prints out the array contents, to help solidify that knowledge.
    And finally, make sure you post whatever you have got after that. We are here to help you get there, not to write it for you, afterall.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Efficient Algorithm for counting number of factors
    By rakeshkool27 in forum C Programming
    Replies: 25
    Last Post: 08-28-2012, 04:04 AM
  2. C Counting Algorithm
    By GrandmaCadburry in forum C Programming
    Replies: 4
    Last Post: 06-09-2011, 10:35 AM
  3. implementing an hours counting algorithm
    By droseman in forum C Programming
    Replies: 6
    Last Post: 02-04-2009, 02:59 AM
  4. Counting sorting operations
    By Cpro in forum C++ Programming
    Replies: 19
    Last Post: 01-25-2008, 09:46 AM
  5. Reading a file, sorting and counting contents, help?
    By mmmm_strawberri in forum C Programming
    Replies: 14
    Last Post: 04-04-2005, 01:21 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21