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

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

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:
    476
    emerth
    Jul 10, 2003
  2. Richard Herring

    Re: Nested sort on a linked list

    Richard Herring, Apr 1, 2004, in forum: C++
    Replies:
    0
    Views:
    390
    Richard Herring
    Apr 1, 2004
  3. fool
    Replies:
    14
    Views:
    502
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    665
    John Carson
    Oct 2, 2006
  5. Navin
    Replies:
    1
    Views:
    685
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page