Selection sort by switching pointers on a linked list = infinite loop?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Selection sort by switching pointers on a linked list = infinite loop?

  1. #1
    Join Date
    Sep 2010
    Posts
    3

    Selection sort by switching pointers on a linked list = infinite loop?

    Please help!
    The following code is supposed to sort the nodes by switching the pointers
    instead of data, but all I get is an infinite loop when I run it.


    #include <stdio.h>
    #include <cstdlib>
    #define HOWMANY 20

    using namespace std;

    class Stack;

    class Node
    {
    public:
    Node (double);
    friend class Stack;
    private:
    double data;
    Node* next;
    };

    #define NodeNULL (Node *)(0)

    Node::Node(double thisdata):data(thisdata),next(NodeNULL)
    {

    }

    class Stack
    {
    public:
    Stack();
    void push(double);
    double pop();
    void selectionsort();
    private:
    Node* top;
    };

    Stack::Stack():top(NodeNULL) { }

    void Stack:ush(double newguy)
    {
    Node* tptr = new Node(newguy);
    tptr->next = top;
    top = tptr;
    }

    double Stack:op()
    {
    Node* tptr;
    double tdata;
    if(top==NodeNULL){
    fprintf(stderr,"empty stack\n");
    exit(1);
    }
    tdata = top->data;
    tptr = top;
    top = top->next;
    delete tptr;
    return(tdata);
    }

    void Stack::selectionsort()
    {

    int icount = 0;
    int count = 0;
    double bestvalue;
    Node *i = top;
    Node *iprev = i;
    Node *j = top;
    Node *jprev = i;
    Node *iprevtemp;
    Node *jprevtemp;
    Node *tempi;
    Node *tempj;
    Node *temp2;
    Node *tempjprev;

    while (i->next != NodeNULL) {

    bestvalue = i->data;
    tempj = i;
    jprev = i;
    j = i->next;

    while (j->next != NodeNULL) {

    if (j->data < bestvalue) {
    bestvalue = j->data;
    tempjprev = jprev;
    tempj = j;
    }

    jprev = j;
    j = j->next;

    }

    //Switching

    tempi = i;
    iprevtemp = iprev;
    jprevtemp = tempjprev;

    jprevtemp->next = tempi;
    iprevtemp->next = tempj;

    temp2 = tempj->next;
    tempj->next = tempi->next;
    tempi->next = temp2;

    i = tempj;

    iprev = i;
    i = i->next;
    }

    }

    double genrand()
    {
    return(((double)(random())+1.0)/((double)(RAND_MAX)+2.0));
    }

    int main(int argc, char** argv)
    {
    int i;
    Stack q;

    srandom(123456789);
    for(i=0;i<HOWMANY;i++) q.push(genrand());
    q.selectionsort();
    for(i=0;i<HOWMANY;i++) printf("%f\n",q.pop());
    }

  2. #2
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Selection sort by switching pointers on a linked list = infinite loop?

    Quote Originally Posted by Blogman View Post
    Please help!
    Please re-edit your post to use proper code tags. It is almost impossible to read as the code is unformatted.

    Second, what debugging have you done, besides just running the program and saying it doesn't work? Did you use your compiler's debugger to solve these issues yourself? What happens if you try to sort something simple, such as three items? What logic flow does your code take?

    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Sep 2010
    Posts
    3

    Re: Selection sort by switching pointers on a linked list = infinite loop?

    Quote Originally Posted by Paul McKenzie View Post
    Please re-edit your post to use proper code tags. It is almost impossible to read as the code is unformatted.

    Second, what debugging have you done, besides just running the program and saying it doesn't work? Did you use your compiler's debugger to solve these issues yourself? What happens if you try to sort something simple, such as three items? What logic flow does your code take?

    Regards,

    Paul McKenzie
    My bad.
    I've used gdb and printf statements to figure out what's going on and it seems to be getting stuck in the the while (j->next != NodeNULL) loop after the first run-through. I think it's because the statements used to switch the pointers aren't working right but I'm really not sure.

    Code:
    // 2. Harder (but sometimes necessary) way: suppose the data in each Node
    //    were massive (not just a double) and would take too long to exchange 
    //    via copying. Perform the exchange by changing only the links in the 
    //    list.
    // 
    //    Hint: add a dummy node to the front (top) of the list, and then
    //    use a one-step-lookahead in all searches.  Except for (two) special
    //    cases, you can just extract both items to be exchanged from the
    //    list and then re-insert them in the proper places.  One special
    //    case is when the two items are actually the same item.  In this case,
    //    nothing needs to be done.  The other is when the two items are adjacent 
    //    in the list.  In this case, extract only the second and insert it in
    //    front of (on top of) the first.
    //    
    #include <stdio.h>
    #include <cstdlib>
    #define HOWMANY 20
    
    using namespace std;
    
    class Stack;
    
    class Node 
    {
    public:
    	Node (double);
    	friend class Stack;
    private:
    	double data;
    	Node* next;
    };
    
    #define NodeNULL (Node *)(0)
    
    Node::Node(double thisdata):data(thisdata),next(NodeNULL)
    {
    
    }
    
    class Stack
    {
    public:
    	Stack();
    	void push(double);
    	double pop();
    	void selectionsort();
    private:
    	Node* top;
    };
    	
    Stack::Stack():top(NodeNULL) { }
    
    void Stack::push(double newguy)
    {
    Node* tptr = new Node(newguy);
    tptr->next = top;
    top = tptr;
    }
    
    double Stack::pop()
    {
    Node* tptr; 
    double tdata;
    if(top==NodeNULL){
    	fprintf(stderr,"empty stack\n");
    	exit(1);
    	}
    tdata = top->data;
    tptr = top;
    top = top->next;
    delete tptr;
    return(tdata);
    }
    
    void Stack::selectionsort()
    {
    
      int icount = 0;
      int count = 0;
      double bestvalue;
      Node *i = top;
      Node *iprev = i;
      Node *j = top;
      Node *jprev = i;
      Node *iprevtemp;
      Node *jprevtemp;
      Node *tempi;
      Node *tempj;
      Node *temp2;
      Node *tempjprev;
    
      while (i->next != NodeNULL) {
    
        bestvalue = i->data;
        tempj = i;
        jprev = i;
        j = i->next;
     
        while (j->next != NodeNULL) {
    
          if (j->data < bestvalue) {
            bestvalue = j->data;
            tempjprev = jprev;
            tempj = j;
          }
    
          jprev = j;
          j = j->next;
          
        }
    
        //Switching
    
         tempi = i;
         iprevtemp = iprev;
         jprevtemp = tempjprev;
    
         jprevtemp->next = tempi;
         iprevtemp->next = tempj;
    
         temp2 = tempj->next;
         tempj->next = tempi->next;
         tempi->next = temp2;
       
         i = tempj;
      
         iprev = i;
         i = i->next;
      }
      
    }
    
    double genrand()
    {
    return(((double)(random())+1.0)/((double)(RAND_MAX)+2.0));
    }
    
    int main(int argc, char** argv)
    {
    int i;
    Stack q;
    
    srandom(123456789);
    for(i=0;i<HOWMANY;i++) q.push(genrand());
    q.selectionsort();
    for(i=0;i<HOWMANY;i++) printf("%f\n",q.pop());
    }

  4. #4
    Join Date
    Sep 2010
    Posts
    3

    Re: Selection sort by switching pointers on a linked list = infinite loop?

    Nevermind, I solved it.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center