- Move the next pointer to the beginning of the structure. [not completely necessary, but useful when casting]

- Use a pointer to a pointer that either points to head or a node->next.

Solved

Posted on 2006-05-23

Learning how to sort a linked list;

The list is made up of a type node:

struct Node {

int item;

Node *next;

};

With "head" pointing to the first node in the list.

---------------------------------------------------------------------

The list I have has these terms: 1456, 59, 1

So, I want to sort this in increasing order:

Node* cur = head;

if (cur->item < cur->next->item){

//do nothing

}

else{

head = cur->next;

//head->next = cur;

cur->next = head->next ;

head->next = cur;

}

Sorts the first two as I want them, but I need a hint on how to build this into a loop to further sort the rest of the list. Of course, I need to expand on this to be able to sort any size list.

thx :)

The list is made up of a type node:

struct Node {

int item;

Node *next;

};

With "head" pointing to the first node in the list.

--------------------------

The list I have has these terms: 1456, 59, 1

So, I want to sort this in increasing order:

Node* cur = head;

if (cur->item < cur->next->item){

//do nothing

}

else{

head = cur->next;

//head->next = cur;

cur->next = head->next ;

head->next = cur;

}

Sorts the first two as I want them, but I need a hint on how to build this into a loop to further sort the rest of the list. Of course, I need to expand on this to be able to sort any size list.

thx :)

18 Comments

- Move the next pointer to the beginning of the structure. [not completely necessary, but useful when casting]

- Use a pointer to a pointer that either points to head or a node->next.

I suppose that the tail element of the list has the following form:

tail->next=NULL;

tail->item=somevalue;

the code here:

Bubble Sort;

boolean Done=TRUE;

do

{

cur=head;

Done=TRUE;

while (cur->next != NULL)

{

if(cur->item > cur->next->item)

{

//swapping

Node* temp = cur->next;

cur->next = cur->next->next;

temp->next = cur;

//change head if cur is equal to head,i.e we are swapping two head elements.

if (cur=head)

{

head=temp;

}

//There is till a swapping.

Done=FALSE;

}//if

else

{

cur=cur->next;

}//else

}//do-while

while (Done ==FALSE);

Brian

However, you don't need to swap nodes but only values (item) though it is still difficult to sort with a singly linked list. After swapping values of B and C like in the sample above, you might need to swap values of A and B accordingly (in the sample it is: after swapping 1 and 1456 you need to swap 59 and 1). However, A isn't available cause the loop's current node is B and B has no pointer to A. There are only two ways out when using a forward link only: first, you restart from head after any swapping. second, you make a recursive sort (what in fact isn't a bubble sort anymore).

I would recommend to turn to a doubly linked list. Then, after swapping values you can go back towards head - always swapping - until you found the position where the currently swapped node value should be inserted. Actually, the bubble sort has turned to some kind of insert sort by that.

Regards, Alex

What is syntax error?

I use temp variable to store pointer so I cannot lose the link.

Thank for your recommend about just swapping value but nodes.

I fix my code now:

(BubbleSort)

boolean Done;

if(head <> NULL)

{

//if list is not empty, sort it.

do

{

cur = head;

Done=TRUE;

while (cur->next != NULL)

{

if(cur->item > cur->next->item)

{

//swapping

<item type> temp = cur->item;

cur->item = cur->next->item;

cur->next->item = temp;

//There is till a swapping.

Done=FALSE;

cur=cur->next;

}//if

}//do-while

while (Done ==FALSE);

}//if.

1.

boolean Done; // bool Done

2.

if (cur=head) // (cur == head)

3.

}//if // improper nesting

else

4.

TRUE FALSE // needs to be true false

5.

cur // variable not defined

>>>> so I cannot lose the link.

if your list is A -> B -> C and cur = B and you swap B and C then A->next is *not* pointing to C but still is pointing to B. That is because there are three nodes involved (prev cur next)

Regards, Alex

1 2 4 is OK. 2 is big mistake, 1,4 is just minor.

3 is wrong. I am not wrong in this case.

5 is wrong, i have declared Node*cur=head.

I think I can improve by use two pointer

Node*prev;

Node*cur;

Do you think it is OK?

Anyway, I thank you very much.

Phuoc H. Nguyen

bool sortYes = false;

do

{ sortYes = false;

Node* placeholder1=head;

Node* placeholder2=head->next;

for (placeholder1; placeholder1 !=NULL; placeholder1 = placeholder1->next){

for (placeholder2; placeholder2 != NULL; placeholder2=placeholder2-

if (placeholder1->term.exp < placeholder2->term.exp){

placeholder1->next = placeholder2->next;

placeholder2->next = placeholder1;

sortYes = true;

}

}

}

}

while(sortYes == true);

need to sort based on the value of term.exp (int) in decreasing order.

any hints?

Your code is same as my previous code and there are mistake itsmeandnobodyelse poited out.

1. You don't need to swap node. Just swap the term part.

2. You make linked list lose link.

A->B->C.

When you swap B and C. A->next->B not C so you lose the list.

if(head != NULL)

{

//if list is not empty, sort it.

do

{

cur = head;

Done=true;

while (cur->next != NULL)

{

if(cur->term.exp < cur->next->term.exp)

{

//swapping

<term type> temp = cur->term;

cur->term = cur->next->term;

cur->next->term = temp;

//There is till a swapping.

Done=false;

cur=cur->next;

}//if

}//do-while

while (Done ==false);

}//if.

bool Done;

if(head != NULL)

{

//if list is not empty, sort it.

do

{

Node* cur = head;

Done=true;

while (cur->next != NULL)

{

if(cur->term.exp < cur->next->term.exp)

{

//swapping

Term temp = cur->term;

cur->term = cur->next->term;

cur->next->term = temp;

//There is till a swapping.

Done=false;

cur=cur->next;

}//if

}

}//do-while

while (Done ==false);

}//if.

bool Done;

if(head != NULL)

{

//if list is not empty, sort it.

do

{

Node* cur = head;

Done=true;

while (cur->next != NULL)

{

if(cur->term.exp < cur->next->term.exp)

{

cout<<"curr "<<cur->term.exp <<endl;

cout<<"next "<<cur->next->term.exp <<endl;

//swapping

Term temp = cur->term;

cur->term = cur->next->term;

cur->next->term = temp;

//There is till a swapping.

Done=false;

}//if <-------------------this bracket not included originally

cur=cur->next;

}

}//do-while

while (Done ==false);

}//if.

..the requirements for the sort function are:

// Postcondition: Terms are sorted in non-increasing order of exponents

// (non-increasing implies that ties are acceptable). Note: No new nodes

// should be created by sort.

so, what are ties??

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**25** Experts available now in Live!