Re: Nested sort on a linked list

Discussion in 'C++' started by Mike Wahler, Apr 1, 2004.

  1. Mike Wahler

    Mike Wahler Guest

    "Mike Jeffers" <> wrote in message
    news:...
    > Hi all,
    >
    > I'm pretty new to programming and need help to do a nested sort on a
    > linked list.
    >
    > Basically I'm sorting a list of structures with names, classroom
    > number and floor level. I can sort in scending order any of the 3
    > values but I need to do a nested sort first with floor, followed by
    > classroom number and finally name.
    >
    > Please tell me where I have gone wrong with this.
    > This is my linked list structure:
    >
    > typedef struct tagCLASSROOMDATA
    > {
    > //added to display addtional info on nozzle configuration
    > char name[128];
    > short floor;
    > short roomnumber;
    > } CLASSROOMDATA;
    >
    > typedef struct CLASSROOMFILEITEM
    > {
    > struct tagCLASSROOMITEM* next;
    > CLASSROOMDATA dt;
    >
    > } CLASSROOMITEM;
    >
    > I am using the algorithm below for my sorting:
    > sortClass( )
    > {
    > BINFILEITEM *p, *q, *r, *s, *temp ;
    > p = r = firstBinfileItem ;
    > while ( p -> next != NULL )
    > {
    > s = q = p -> next ;
    > while ( q != NULL )
    > {
    > if ( p -> dt.floor > q -> dt.floor )
    > {
    > if ( p -> next == q ) /* Adjacent Nodes */
    > {
    > if ( p == firstBinfileItem )
    > {
    > p -> next = q -> next ;
    > q -> next = p ;
    > temp = p ;
    > p = q ;
    > q = temp ;
    > firstBinfileItem = p ;
    > r = p ;
    > s = q ;
    > q = q -> next ;
    > }
    > else
    > {
    > p -> next = q -> next ;
    > q -> next = p ;
    > r -> next = q ;
    > temp = p ;
    > p = q ;
    > q = temp ;
    > s = q ;
    > q = q -> next ;
    > }
    > }
    > else
    > {
    > if ( p == firstBinfileItem )
    > {
    > temp = q -> next ;
    > q -> next = p -> next ;
    > p -> next = temp ;
    > s -> next = p ;
    > temp = p ;
    > p = q ;
    > q = temp ;
    > s = q ;
    > q = q -> next ;
    > firstBinfileItem = p ;
    > }
    > else
    > {
    > temp = q -> next ;
    > q -> next = p -> next ;
    > p -> next = temp ;
    > r -> next = q ;
    > s -> next = p ;
    > temp = p ;
    > p = q ;
    > q = temp ;
    > s = q ;
    > q = q -> next ;
    > }
    > }
    > }
    > else
    > {
    > s = q ;
    > q = q -> next ;
    > }
    > }
    > r = p ;
    > p = p -> next ;
    > }
    > }
    >
    > Any help will be most appreciated, thanks!


    Given objects 'left' and 'right' being compared:

    if(left.key1 == right.key1)
    {
    if(left.key2 == right.key2)
    {
    if(left.key3 < right.key3)
    swap(left, right);
    }
    else
    {
    if(left.key2 < right.key2)
    swap(left, right);
    }
    }
    else
    if(left.key1 < right.key1)
    swap(left, right);
    }

    -Mike
     
    Mike Wahler, Apr 1, 2004
    #1
    1. Advertisements

  2. Mike Wahler

    Bill Weston Guest

    "Mike Wahler" <> wrote in message news:<n4Jac.9633$>...
    > "Mike Jeffers" <> wrote in message
    > news:...
    > > Hi all,
    > >
    > > I'm pretty new to programming and need help to do a nested sort on a
    > > linked list.
    > >
    > > Basically I'm sorting a list of structures with names, classroom
    > > number and floor level. I can sort in scending order any of the 3
    > > values but I need to do a nested sort first with floor, followed by
    > > classroom number and finally name.
    > >
    > > Please tell me where I have gone wrong with this.
    > > This is my linked list structure:

    [snip]

    > > Any help will be most appreciated, thanks!

    >
    > Given objects 'left' and 'right' being compared:
    >
    > if(left.key1 == right.key1)
    > {
    > if(left.key2 == right.key2)
    > {
    > if(left.key3 < right.key3)
    > swap(left, right);
    > }
    > else
    > {
    > if(left.key2 < right.key2)
    > swap(left, right);
    > }
    > }
    > else
    > if(left.key1 < right.key1)
    > swap(left, right);
    > }
    >
    > -Mike


    Or, for a shortish list and an easy life, and assuming that your basic
    sort algorithm does not rearrange equal elements, just do the sort
    three times...

    first sort on key3,
    then sort on key2,
    then sort on key1.

    Bill Weston
     
    Bill Weston, Apr 1, 2004
    #2
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    708
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    717
    emerth
    Jul 10, 2003
  3. Kent
    Replies:
    10
    Views:
    703
    Tom St Denis
    Oct 24, 2003
  4. fool
    Replies:
    14
    Views:
    803
    Barry Schwarz
    Jul 3, 2006
  5. joshd
    Replies:
    12
    Views:
    952
    John Carson
    Oct 2, 2006
  6. jawdoc
    Replies:
    9
    Views:
    1,049
    Chris Thomasson
    Mar 10, 2008
  7. mac
    Replies:
    1
    Views:
    1,955
    Jens Thoms Toerring
    May 27, 2008
  8. Navin
    Replies:
    1
    Views:
    1,135
    Ken Schaefer
    Sep 9, 2003
Loading...