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

• September 25th, 2010, 03:49 PM
Blogman
Selection sort by switching pointers on a linked list = infinite loop?
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());
}
• September 25th, 2010, 04:12 PM
Paul McKenzie
Re: Selection sort by switching pointers on a linked list = infinite loop?
Quote:

Originally Posted by Blogman

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
• September 25th, 2010, 05:01 PM
Blogman
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

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