Thread: sorting structure members using pointers

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    14

    sorting structure members using pointers

    Hello, I am working through the book C Primer Plus by Stephen Prata, and am stuck on problem 3 in Chapter 14. I have no classmates or teachers, and cannot for the life of me see why this thing won't sort.

    The structure, along with the function that will sort the members that are the 'title' strings, is here:e in the sorting part, though I am using a simple "bubble sort" that should work.

    Can anyone see what I am missing?

    Code:
    struct book {                   /* set up book template */
            char title[MAXTITL];
            char author[MAXAUTL];
            float value;
    };
    
    /* this function will output the books by alpabetized titles */
    
    void print_by_title(const struct book * ptr, int totl)
    {
            int i;                          /* an index */
                                            /* i will range from 0 to < totl */
            int array[totl];                /* this array will hold the indices of */
                                            /* the books, but will be in alphabetical */
                                            /* order. */
            int outer;                      /* used in sorting */
            int inner;                      /* used in sorting */
            int temp;                       /* used in sorting */
    
            /* initialize array[] */
            for(i = 0; i < totl; i++)
                    array[i] = i;
    
            /* Alphabetize the list according to titles.  That is, */
            /* sort the indices of array[]. */
    
            for(outer = 0; outer < totl; outer++)
                    for(inner = 0; inner < (totl - 1); inner++)
                    {
                            if(strcmp((ptr + inner)->title, (ptr + (inner + 1))->title) > 0)
                            {
                                    temp = array[inner + 1];
                                    array[inner + 1] = array[inner];
                                    array[inner] = temp;
                            }
                    }
    
            /* print out the book list according to alphabetized titles */
            printf("\n");
            printf("Here are the books alphabetized by title:\n");
            printf("\n");
            for(i = 0; i < totl; i++)
                    printf("%s by %s, $%.2f\n", (ptr + array[i])->title,
                                    (ptr + array[i])->author, (ptr + array[i])->value);
    Robert
    Last edited by robstr12; 07-25-2005 at 01:08 PM.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    With a bubblesort, you have to do the sort over and over again until no swaps took place.

    That's not your whole function, right?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    When sorting an index table without modifying the data table, you need to make sure that the changes to the index table are reflected in the comparisons for the sort. Here is an algorithm that does this, and also uses a mandatory optimization for bubble sort:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct test {
      char *str;
      int val;
    };
    
    void print_sorted ( struct test a[], int n );
    
    int main ( void )
    {
      struct test a[] = {
        {"this", 123},
        {"is", 456},
        {"a", 789},
        {"test", 000}
      };
    
      print_sorted ( a, 4 );
    
      return 0;
    }
    
    void print_sorted ( struct test a[], int n )
    {
      int i, j, save;
      int *index = malloc ( n * sizeof *index );
    
      if ( index == NULL )
        return;
    
      for ( i = 0; i < n; i++ )
        index[i] = i;
    
      for ( i = n - 1; i > 0; i-- ) {
        int swapped = 0;
    
        for ( j = 0; j < i; j++ ) {
          if ( strcmp ( a[index[j]].str, a[index[j + 1]].str ) > 0 ) {
            save = index[j];
            index[j] = index[j + 1];
            index[j + 1] = save;
            swapped = 1;
          }
        }
    
        if ( !swapped )
          break;
      }
    
      for ( i = 0; i < n; i++ )
        printf ( "%s : %d\n", a[index[i]].str, a[index[i]].val );
    
      free ( index );
    }
    Notice how I used index in the comparison too. That way you don't end up comparing things that you've already compared and botching up the order.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    14
    Quote Originally Posted by dwks
    With a bubblesort, you have to do the sort over and over again until no swaps took place.

    That's not your whole function, right?
    Actually, I did neglect to include the terminal bracket "}", but that is all I did not include.

    As I have read documentation about the "bubble sort" (knowing that it is the "worst" kind of sorting algorithm, but I just want to get the dang thing to work right now), I saw from various sources that if you looped through the outer loop once for each element in the set, that would be sufficient, even in the worst case scenario, unless I misuderstood.

    Thank you, dwks.

    @ Prelude:
    Thank you, too,
    and I will have to take my time to look carefully at what you have posted there.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >knowing that it is the "worst" kind of sorting algorithm
    Well, it's easy to come up with something worse than bubble sort, but you're not likely to see anything worse in real code.

    >but I just want to get the dang thing to work right
    In my opinion, selection sort is much easier to get right the first time than bubble sort, and it has more useful performance properties than bubble sort.
    My best code is written with the delete key.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    14
    Well, here we go...
    Looks like I will have another look at the "selection sort" type of algorithm as I work through this. That is good.

    I'm in a position to tackle this now.

    hehe... I'll get this C language, yes. I will just keep on hacking away until I finally understand it!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. global structure pointers
    By threahdead in forum Linux Programming
    Replies: 2
    Last Post: 03-13-2003, 12:21 PM
  2. structure members outside main
    By threahdead in forum C Programming
    Replies: 5
    Last Post: 03-09-2003, 07:34 AM
  3. API "Clean Up" Functions & delete Pointers :: Winsock
    By kuphryn in forum Windows Programming
    Replies: 2
    Last Post: 05-10-2002, 06:53 PM
  4. structure pointers
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 10-17-2001, 11:04 AM