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

+1 vote
122 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

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.

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
``````
sorry but it give me error .. !!
No its not it is working fine
Similar Questions