3 Replies - 3598 Views - Last Post: 25 September 2010 - 11:30 PM Rate Topic: -----

#1 Blogman  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 6
  • Joined: 25-September 10

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

Posted 25 September 2010 - 03:55 PM

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.

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.

Any ideas?

 
#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());
}




Is This A Good Question/Topic? 0
  • +

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

#2 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 988
  • View blog
  • Posts: 5,135
  • Joined: 28-September 06

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

Posted 25 September 2010 - 06:20 PM

For the moment, while you debug this, reduce "HOWMANY" to a smaller number, say 3.

Write a 'printStack()' method for the Stack class.
This should print the whole stack out non-destructively (i.e. pop() is not good, you want to leave the stack in good shape not pulled to pieces).
After each sort step call the printStack() method to see what state the stack is in.

I had a quick look at your code in a debugger and I can see what is concerning you (as in I see what you are talking about with the looping - not that the cause leapt out at me in the 5 minutes I gave it) but I didn't try very hard to fix it.

Anyway are you still having trouble or is this fixed at your end now?
Was This Post Helpful? 1
  • +
  • -

#3 Blogman  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 6
  • Joined: 25-September 10

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

Posted 25 September 2010 - 10:46 PM

View Postjanotte, on 25 September 2010 - 05:20 PM, said:

For the moment, while you debug this, reduce "HOWMANY" to a smaller number, say 3.

Write a 'printStack()' method for the Stack class.
This should print the whole stack out non-destructively (i.e. pop() is not good, you want to leave the stack in good shape not pulled to pieces).
After each sort step call the printStack() method to see what state the stack is in.

I had a quick look at your code in a debugger and I can see what is concerning you (as in I see what you are talking about with the looping - not that the cause leapt out at me in the 5 minutes I gave it) but I didn't try very hard to fix it.

Anyway are you still having trouble or is this fixed at your end now?


It finally worked after 2 more hours of debugging. Just running through different possibilities, I found many things that needed to be revised. Thanks!
Was This Post Helpful? 0
  • +
  • -

#4 janotte  Icon User is offline

  • code > sword
  • member icon

Reputation: 988
  • View blog
  • Posts: 5,135
  • Joined: 28-September 06

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

Posted 25 September 2010 - 11:30 PM

Ah good news and well done.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1