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

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

1. Junior Member
Join Date
Sep 2010
Posts
3

## 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)ata(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. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

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

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

3. Junior Member
Join Date
Sep 2010
Posts
3

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

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
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. Junior Member
Join Date
Sep 2010
Posts
3

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

Nevermind, I solved it.

#### Posting Permissions

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