Thread: Sorting a string

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    175

    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...

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Well you could use the library qsort() function in stdlib.h
    There are plenty of example uses on this forum
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jun 2004
    Posts
    84
    Or if you press F1 in VC++ it will throw you this: http://msdn.microsoft.com/library/de..._crt_qsort.asp

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  5. #5
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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$
    If you understand what you're doing, you're not learning anything.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Holy Deja Vu, Batman!

    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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
    If you understand what you're doing, you're not learning anything.

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Apr 2004
    Posts
    210
    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 ?

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

  13. #13
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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.
    If you understand what you're doing, you're not learning anything.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sorting 2D string array
    By sureshhewa in forum C Programming
    Replies: 14
    Last Post: 07-27-2008, 01:30 PM
  2. Inheritance Hierarchy for a Package class
    By twickre in forum C++ Programming
    Replies: 7
    Last Post: 12-08-2007, 04:13 PM
  3. Custom String class gives problem with another prog.
    By I BLcK I in forum C++ Programming
    Replies: 1
    Last Post: 12-18-2006, 03:40 AM
  4. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM
  5. creating class, and linking files
    By JCK in forum C++ Programming
    Replies: 12
    Last Post: 12-08-2002, 02:45 PM