Sorting Strings

[BigDrone]

Ok i have a linked list, each node in the list contains a string for a first, and a string for the last name. I also have a year stored as an int. i am tring to sort the list first by last name, then first, then by year. I was thinking of using a merge sort but am not sure if thats the best approach. Thanks for the help.

 

[BigDrone]

This is actually for a program i'm writting to open GEDCOM files and set them up for Geneology Work. I have sample code i can supply if needed.

 

[Zyrenthian]

I would use qsort provided in sort.h I hate writing up sorting algoritms

Matt

 

[Salem]

Here's my suggestion using qsort()

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
  struct node *next;
  char         fname[20];
  char         lname[20];
  int          age;
} node_t;

// list append function, which you should have already
node_t *append ( node_t *head, char fname[], char lname[], int age ) {
  node_t *newnode = malloc ( sizeof *newnode );
  newnode->next = NULL;
  strcpy( newnode->fname, fname );
  strcpy( newnode->lname, lname );
  newnode->age = age;
  if ( head == NULL ) {
    head = newnode;
  } else {
    node_t *temp = head;
    while ( temp->next != NULL ) temp = temp->next;
    temp->next = newnode;
  }
  return head;
}

// list length, which you may have already
int length ( node_t *head ) {
  int count = 0;
  while ( head != NULL ) {
    head = head->next;
    count++;
  }
  return count;
}

// create an array of pointers to each member of the list
void copy_ptrs ( node_t *head, node_t **arr ) {
  int count = 0;
  while ( head != NULL ) {
    arr[count++] = head;
    head = head->next;
  }
}

// example compare functions
int cmp_fname ( const void *pa, const void *pb ) {
  const node_t **a = pa;
  const node_t **b = pb;
  return strcmp( (*a)->fname, (*b)->fname );
}
int cmp_age ( const void *pa, const void *pb ) {
  const node_t **a = pa;
  const node_t **b = pb;
  int ia = (*a)->age;
  int ib = (*b)->age;
  if ( ia < ib ) return -1;
  if ( ia > ib ) return +1;
  return 0;
}

int main(void) {
  int       list_len, i;
  node_t   *list = NULL;
  node_t  **array;

  // create a list
  list = append( list, &quot;fred&quot;, &quot;flintstone&quot;, 35 );
  list = append( list, &quot;wilma&quot;, &quot;flintstone&quot;, 33 );
  list = append( list, &quot;pebbles&quot;, &quot;flintstone&quot;, 5 );
  list = append( list, &quot;barney&quot;, &quot;rubble&quot;, 29 );
  list = append( list, &quot;betty&quot;, &quot;rubble&quot;, 27 );
  list = append( list, &quot;bam-bam&quot;, &quot;rubble&quot;, 4 );

  // flatten the current list into an array
  list_len = length( list );
  array = malloc ( list_len * sizeof *array );
  copy_ptrs ( list, array );

  // having got an array, you can qsort() it multiple times
  // without any further difficulty.
  qsort( array, list_len, sizeof *array, cmp_fname );
  for ( i = 0 ; i < list_len; i++ ) {
    printf( &quot;%s %s %d\n&quot;, array[i]->fname, array[i]->lname, array[i]->age );
  }

  qsort( array, list_len, sizeof *array, cmp_age );
  for ( i = 0 ; i < list_len; i++ ) {
    printf( &quot;%s %s %d\n&quot;, array[i]->fname, array[i]->lname, array[i]->age );
  }
  return 0;
}

--

 

[tokra]

If you implement the == operator and the < operator, you can store your struct in a standard container like a list or vector and use the containers built in sort algorithim.

WR

 

[BigDrone]

Thanks a lot for the help, i implemented the quicksort and i got the names printing out right. Appreciate the help