qsort() really seems to suck at this (unless I did something wrong in my program):
Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>
int compare(const void *ptr1, const void *ptr2)
{
return *(char *)ptr1 > *(char *)ptr2;
}
void get_diff(struct timeval *b, struct timeval *e, struct timeval *d)
{
d->tv_usec = e->tv_usec - b->tv_usec;
d->tv_sec = e->tv_sec - b->tv_sec + (d->tv_usec < 0);
if(d->tv_usec < 0)
d->tv_usec += 1000000;
}
int main(void)
{
char *str = "This is a string that needs to be sorted.";
char sorted[4096], *p;
int i, j, k, count[128];
struct timeval begin, end, diff;
gettimeofday(&begin, NULL);
for(i = 0;i < 10000;++i)
{
strcpy(sorted, str);
qsort(sorted, strlen(sorted), 1, compare);
}
gettimeofday(&end, NULL);
puts("Method: qsort");
get_diff(&begin, &end, &diff);
printf("Time : %d.%06d\n", (int)diff.tv_sec, (int)diff.tv_usec);
printf("Result: %s\n", sorted);
gettimeofday(&begin, NULL);
for(i = 0;i < 10000;++i)
{
memset(count, 0, sizeof(int)*128);
for(p = str;*p;p++)
count[(int)*p]++;
for(p = sorted, j = 0;j < 128;++j)
if(count[j])
for(k = 0;k < count[j];++k)
*p++ = j;
*p = '\0';
}
gettimeofday(&end, NULL);
puts("Method: character count");
get_diff(&begin, &end, &diff);
printf("Time : %d.%06d\n", (int)diff.tv_sec, (int)diff.tv_usec);
printf("Result: %s\n", sorted);
return 0;
}
Code:
itsme@dreams:~/C$ ./strsort
Method: qsort
Time : 0.516076
Result: .Taabddeeeeghhiiinnoorrsssssttttt
Method: character count
Time : 0.079353
Result: .Taabddeeeeghhiiinnoorrsssssttttt
itsme@dreams:~/C$