top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

My question about comparing run time performance of Counting sort !!

+1 vote
842 views

1- Implement the counting sort algorithm using C++
2- use data of different size in your code 10000,100000,1000000

posted Apr 18, 2014 by As M Ob

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
I could not understand anything from the question statement, and its description. Can you please edit and ask to the point also put the proper question title...
I also can not make out what is the question? Please edit and provide info...
http://www.comp-psyche.com/2014/08/counting-sort-program-in-c.html

See the above link. Counting sort is explained here with algorithm and code. May be it might be helpful. Number are sorted using counting sort.

1 Answer

0 votes

Credit: http://www.geeksforgeeks.org/counting-sort/

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Let us understand it with the help of an example.

For simplicity, consider the data in the range 0 to 9.
Input data: 1, 4, 1, 2, 7, 5, 2
1) Take a count array to store the count of each unique object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0 0

2) Modify the count array such that each element at each index
stores the sum of previous counts.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 4 4 5 6 6 7 7 7

The modified count array indicates the position of each object in
the output sequence.

3) Output each object from the input sequence followed by
decreasing its count by 1.
Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
Put data 1 at index 2 in output. Decrease count by 1 to place
next data 1 at an index 1 smaller than this index.

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.

#include <stdio.h>
#include <string.h>
#define RANGE 255

void countSort(char *str)
{
    char output[strlen(str)];

    // Create a count array to store count of inidividul characters and
    // initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));

    // Store count of each character
    for(i = 0; str[i]; ++i)
        ++count[str[i]];

    // Change count[i] so that count[i] now contains actual position of
    // this character in output array
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];

    // Build the output character array
    for (i = 0; str[i]; ++i)
    {
        output[count[str[i]]-1] = str[i];
        --count[str[i]];
    }

    // Copy the output array to str, so that str now
    // contains sorted characters
    for (i = 0; str[i]; ++i)
        str[i] = output[i];
}

int main()
{
    char str[] = "queryhome";

    countSort(str);

    printf("Sorted string is %s\n", str);
    return 0;
}

Output

Sorted string is eehmoqruy
answer Apr 19, 2014 by Meenal Mishra
sorry but it give me error .. !!
No its not it is working fine
Similar Questions
+3 votes

1) Implement both algorithms
2) Test both on three cases of data:
a) sorted in increase order,
b) sorted in decrease order,
c) randomly
3) Use data of different sizes: 10000, 100000, 1000000.

+1 vote

if input this Data size 10000,100000,1000000

+6 votes

First see this example: let you have a number 8 which is divisible by 4 which is square of 2 and 27 which is divisible by 9 which is square of 3.I need a solution for numbers input from 1 to 10^18.hope for efficient program written in any programming language.
Thanks in advance.

...