Help with SORT...

22Driver · #1 02-Apr-2005, 23:39

I am trying to figure out why this sort program doesn't work. It is code to sort a linked list and it works partially, but not totally. Here is the code and I will explain the input/output after the code:

CPP / C++ / C Code:

void sList::sorted()
{
  sListNode *temp = head;

    for( sListNode *cur = head; cur != end; cur = cur->next )
    {
      for( sListNode *j = cur->next; j != end; j = j->next )
      {
        if( cur->data > j->data )
        {
          temp->data = j->data;
          j->data = cur->data;
          cur->data = temp->data;
        }
     }
   }
}

I insert the numbers {23, 7, 12, 42, 0} into a linked list (0 being the identifier for the end of list) and the output I get when I sort it is:

7 7 12 42

When it is run through the first time, I output the data before and after the if statement (using some cout statements), I get that cur = 23, temp = 23, head = 23, and j = 7 and then it becomes cur = 7, temp = 7, head = 7, and j = 7. What is causing it to bypass the line j->data = cur->data? I used the debugger and watched it and it is like the line isn't even there. If I take out the line temp->data = j->data, then the line j->data = cur->data works fine. I have been wracking my brain on this for days and can't figure it out. I have tried all kinds of crazy things to get it to change with no luck. Can anyone help me or point me in the right direction?

Thanks in advance.

Mike

davekw7x · #2 03-Apr-2005, 09:04

Quote:

Originally Posted by 22Driver

I am trying to figure out why this sort program doesn't work. It is code to sort a linked list and it works partially, but not totally. Here is the code and I will explain the input/output after the code:

Look at this:

CPP / C++ / C Code:

//
        sListNode *temp = head;

Then, when you perform the swap:

CPP / C++ / C Code:

//
          temp->data = j->data;
          j->data = cur->data;
          cur->data = temp->data;

You are always swapping the data into the head of the list (since the value of temp is equal to head --- which I assume is a pointer to the head of the list).

Maybe you could do this:

CPP / C++ / C Code:

//
         sListNode temp;

then

CPP / C++ / C Code:

//
          temp.data = j->data;
          j->data = cur->data;
          cur->data = temp.data;

Now, maybe this works (or maybe not, since I have no way of knowing if the linked list is set up properly, and what the values of head and end are). However... I think maybe you are missing the point (or maybe I am missing the point) of the assignment.

The idea of sorting a linked list usually means changing the links, not swapping data. After all, if the list itself remains the same and you are only changing data, why use a list at all? Just use an array of ints (or an array of structs, or whatever).

Regards,

Dave

22Driver · #3 03-Apr-2005, 14:22

Dave,

I appreciate you replying to my dilemna, but it isn't the assignment that is the point.

If I am changing only the data, then why does the linked list print out 7 7 12 42. What happened to the 23 is the point? Where did it go? Regardless if I assign sListNode *temp = head, the node assigned to head changed to 7, but when j->data was supposed to become 23, it didn't and I am trying to find out why.

When I use my print function the list has become just what I said up above...7 7 12 42. What happend to the 23? The list changed and yes it may have something to do with the way I make the list (which is just a simple insert node at the beginning of a linked list...nothing fancy), but I don't think so, because if I call my print function before I call sort, it prints out exactly what I entered...23, 7, 12, 42.

Thanks in advance for any help.

Mike

davekw7x · #4 03-Apr-2005, 15:19

Quote:

Originally Posted by 22Driver

Dave,

I appreciate you replying to my dilemna, but it isn't the assignment that is the point.

Did you make this change?

Quote:

Originally Posted by davekw7x

Look at this:

CPP / C++ / C Code:

//
        sListNode *temp = head;

Then, when you perform the swap:

CPP / C++ / C Code:

//
          temp->data = j->data;
          j->data = cur->data;
          cur->data = temp->data;

You are always swapping the data into the head of the list (since the value of temp is equal to head --- which I assume is a pointer to the head of the list).

Maybe you could do this:

CPP / C++ / C Code:

//
         sListNode temp;

then

CPP / C++ / C Code:

//
          temp.data = j->data;
          j->data = cur->data;
          cur->data = temp.data;

The way you are doing it, your code sets temp to point to the head, so that whens a swap occurs, j->data gets into the head. And the head data gets into cur->data

What you really want to happen is for a swap to put j->data into cur->data and cur->data into j->data.

I'm not sure exactly how you set everything up, but here's your function with lots of debug statements. If you don't understand what happened to the first element of your array, look at the results before and after the swap.

(I altered it slightly so that you can uncomment a single statement to compare the original way with the method using the change that I suggested.)

CPP / C++ / C Code:

void sorted()
{
  sList temp;
  sList *ptemp = &temp; // this is the good thing
  //ptemp = head; // uncomment this to see the bad thing

  cout << "In sorted(), before sorting: " << endl;
  printlist();

  for( sList *cur = head; cur != end; cur = cur->next ) {
    for( sList *j = cur->next; j != end; j = j->next ) {
      cout << "cur = " << cur << ", cur->data = " << cur->data
           << ", j = " << j << ", j->data = " << j->data << endl;
      if( cur->data > j->data ) {
        cout << "swap: " << endl;
        cout << "head = " << head
             << ", cur = " << cur
             << ", j = " << j << endl;


        ptemp->data = j->data;
        j->data = cur->data;
        cur->data = ptemp->data;

        cout << "now head = " << head 
             << ", head->next = " << head->next << endl;

        cout << "After swap:" << endl;
        printlist();
        cout << endl;
      }
    }
  }

}

void printlist ()
{
  cout << "List: " << endl;
  sList *headnext = head->next;
  for (sList *cur = head; cur != end; cur = cur->next) {
    cout << cur->data << endl;
  }
  cout << endl;
}

This seems to work.
Now, uncomment the third statement in sorted(), so that it does what your original program does.

Does this look kind of messy, and kind of tedious? Well, yes. That's what you get sometimes. Can you figure this stuff out for yourself? Well, put in print statements in and around your problem areas until you zero in on it. It's still faster, I claim, than posting a request for assistance and waiting for a helpful response.

Regards,

Dave

22Driver · #5 03-Apr-2005, 18:53

Dave,

I understand what you are saying about asking for help and trust me in all my years of programming in other languages, I only asked for help once I was at an end right before starting the project from scratch. I guess I am at that point now. So I appreciate the help, but I will move on elsewhere.

Mike

davekw7x · #6 03-Apr-2005, 19:23

Quote:

Originally Posted by 22Driver

Dave,

I understand what you are saying about asking for help and trust me in all my years of programming in other languages, I only asked for help once I was at an end right before starting the project from scratch. I guess I am at that point now. So I appreciate the help, but I will move on elsewhere.

Mike

I didn't mean that you shouldn't ask for help (that's what we are here for). What I meant was:

I tried to indicate why your function didn't work. I realize that my narrative may not have been very complete or satisfactory, but I assure you that your way didn't work, and mine did, to the extent that I could test it --- that is with your data.

I gave you a way to "fix" your function. (Did you try it?)

I showed you the way that I get to the bottom of things: lots of print statements that include printing out the values of pointers as well as the values of things that they point to at each step of the sort.

If there is anything else that I can do, I will try to think of it, but I'm kind of stumped.

It's still faster, I claim, for you to try some of these things, and if you think of better things to try, then that's even better.

Regards,

Dave

22Driver · #7 04-Apr-2005, 06:52

Dave,

I understand what you are saying about your method and since I didn't give you the whole picture I can understand you way working for your system, but that doesn't mean it will work with mine (not your fault).

Yes, I do the same thing you do. If you were to ever see one of my programs in progress you would look at the code and think I get paid premium dollar for every <cout> statement I put in there. I use them extensively in all of my programs to help in debugging problems as the debugger doesn't always do what I need, so they are not new to me.

What I am saying is that to make you method work, it will require a lot more work due to all the changes and my having to shoe horn it into my program (since I didn't give you the whole program) that it will probably behoove me to just start over and try again with fresh code.

What I was really trying to figure out is what happened to the 23? Where did it go? It wasn't the temp line that caused it to get lost. Somewhere in the algorithm it got lost and I was trying to figure out why, not necessarily get a quick fix for my code. If I can figure out why the 23 (or any other item at the beginning of my swap) disappeared, then I can figure out how to fix it.

I do really appreciate your help and I will take another look at fixing what you said to see what it does, but I think I would be better served (for my own education) to just start from scratch.

Thanks again.

Mike

22Driver · #8 05-Apr-2005, 20:20

Dave,

I started the code over from new (basically modified another linked list program that I did) worked it all in and then went back to the basic sort code here...and it works now. Thanks for all the help.

Just for my edification about what is going on, I have a few questions:

1. sList temp; - What exactly is this pointing to?

2. sList *ptemp = &temp; - If I understand this correctly, it is like making a copy of temp and stuffing it into ptemp...is that right?

Thanks again for all the help.

Mike

davekw7x · #9 05-Apr-2005, 22:22

Quote:

Originally Posted by 22Driver

Dave,

I started the code over from new (basically modified another linked list program that I did) worked it all in and then went back to the basic sort code here...and it works now. Thanks for all the help.

Just for my edification about what is going on, I have a few questions:

1. sList temp; - What exactly is this pointing to?

2. sList *ptemp = &temp; - If I understand this correctly, it is like making a copy of temp and stuffing it into ptemp...is that right?

Thanks again for all the help.

Mike

CPP / C++ / C Code:

sList temp; /* declare a new local variable temp. its type is sList (from the typedef */
sList *ptemp = &temp; /* declare a new local variable ptemp. its type is pointer */
/* to an sList. Its value is initialized to "the address of the variable temp */

I didn't really nead to declare the pointer, (I could have just used temp). I used pTemp so that I could use the same notation as before.

To access the data member of temp, you can use either of the following:

CPP / C++ / C Code:

temp.data = xxx;
pTemp->data = xxx;

The results are identical.

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Merge sort on a linked list	Temujin_12	C++ Forum	1	06-Mar-2008 20:33
bucket sort problem	ap6118	C++ Forum	3	15-Apr-2005 18:02
[GIM] gim.h	dsmith	C Programming Language	0	18-Jan-2005 08:48
insert sort	saphir55	C Programming Language	4	06-Dec-2004 14:00
help with Sort arrays/Size	justachessgame	C Programming Language	1	12-Nov-2004 23:46