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::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());
}
Re: Selection sort by switching pointers on a linked list = infinite loop?
Quote:
Originally Posted by
Blogman
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
Re: Selection sort by switching pointers on a linked list = infinite loop?
Quote:
Originally Posted by
Paul McKenzie
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());
}
Re: Selection sort by switching pointers on a linked list = infinite loop?
