Sorting a string

Hello All,

I want to sort a string. And In have array of such integers.

e.g "program" should become "agomprr"

But first algo comes to my mind is bubble sorting the string. I do not wish to do this as my string size may increase at later point of time.

Second is frequency table. Declare an array of 64 characters. Go on adding the alphabets as you read from string. And put back into string as you read array. This will in O(2n) .

DO you have any cuter method to sort a string.

Basically, I have been told to find, whether in given array of string, find if there are any annagrams.

Please let me know...

Well you could use the library qsort() function in stdlib.h
There are plenty of example uses on this forum

Or if you press F1 in VC++ it will throw you this: http://msdn.microsoft.com/library/de..._crt_qsort.asp

>But first algo comes to my mind is bubble sorting the string.
Train yourself to think of the standard library's qsort first, then of shellsort. :)

>I do not wish to do this as my string size may increase at later point of time.
How much of an increase are we talking about? Bubble sort is more acceptable for small sets (even though there are better alternatives that are just as easy). Before you go writing a complicated sorting algorithm, profile the code with bubble sort and see if it's fast enough with the amount of expected string growth. Even if you end up using a library function as you should, it'll be a learning experience.

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$

---

>qsort() really seems to suck at this
That's a quality of implementation issue (qsort's, not yours :)). That's why you always profile to test your performance expectations.

Well I get much closer times when I use a proper compare function

Code:

---

int compare(const void *ptr1, const void *ptr2)
{
  const char *p1 = ptr1;
  const char *p2 = ptr2;
  if ( *p1 < *p2 ) return -1;
  if ( *p1 > *p2 ) return +1;
  return 0;
/*  return *(char *)ptr1 > *(char *)ptr2; */
}

---

Yours is only capable of returning 0 or 1, so qsort() has to work a lot harder (I'm impressed that it manages) to sort your array.

Holy Deja Vu, Batman!

Quzah.

I still get about the same time with the fixed compare() function (how embarassing!)

Code:

---

Method: qsort
Time  : 0.593415
Result:        .Taabddeeeeghhiiinnoorrsssssttttt
Method: character count
Time  : 0.079383
Result:        .Taabddeeeeghhiiinnoorrsssssttttt

---

Quote:

---

Originally Posted by itsme86

I still get about the same time with the fixed compare() function (how embarassing!)

Code:

---

Method: qsort
Time  : 0.593415
Result:        .Taabddeeeeghhiiinnoorrsssssttttt
Method: character count
Time  : 0.079383
Result:        .Taabddeeeeghhiiinnoorrsssssttttt

---

---

Well of course you do! Add this:

Code:

---

  printf("Result: %s\n", sorted);
  {
    int x;
    for( x = 0; sorted[x]; x++ )
        printf("%c is %d\n", sorted[x], sorted[x] );
  }
  return 0;

---

Don't smack yourself in the forehead too hard! ;)

Quzah.

Code:

---

gettimeofday(&begin, NULL);
  for(i = 0;i < 10000;++i)
  {
    strcpy(sorted, str);
    qsort(sorted, strlen(sorted), 1, compare);
  }
  gettimeofday(&end, NULL);

---

You don't do a stringcopy for your own implementation. To get a fair comparison, you'll have to do it in your method, too. Even if it isn't neccessary.

btw, is it possible to inline compare() here ?

>btw, is it possible to inline compare() here ?
Good question. :) As far as I can tell (according to the C99 standard), the answer is yes. If you're not using C99 then the anwer is implementation-dependent based on your compiler's features and optimization capabilities.

Quote:

---

Originally Posted by Nyda

Code:

---

gettimeofday(&begin, NULL);
  for(i = 0;i < 10000;++i)
  {
    strcpy(sorted, str);
    qsort(sorted, strlen(sorted), 1, compare);
  }
  gettimeofday(&end, NULL);

---

You don't do a stringcopy for your own implementation. To get a fair comparison, you'll have to do it in your method, too. Even if it isn't neccessary.

btw, is it possible to inline compare() here ?

---

I tried to encapsulate everything that needed to be done in the loop for each. Since the second method would never need to do the strcpy() then it doesn't do it. Having to do the strcpy() is a "disadvantage" of the qsort method I guess is a way of looking at it.