bingie
asked on
Sorting...
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 :)
Node* cur = head;
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);
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);
If you're not worried about effiency, you could create a flag called 'noSwaps' set it equal to true before a loop is run, then during the loop you can compare to adjacent values, and swap as necessary and keep going (if you swap set your flag to false). Then continue in the list swapping adjacent values. When the loop is done, if noSwaps = true then you are done, the list is sorted, if noSwaps = false you need to do another iteration.
Brian
Brian
Btw, the methoed I mentioned is effectivly a bubble sort algorithm :)
Hi BrianGEFF719,
Yours are same as my post!
Phuoc H. Nguyen
Yours are same as my post!
Phuoc H. Nguyen
phuocnh,
You're right...sorry about that, I didn't look at your code when I made my post.
Brian
You're right...sorry about that, I didn't look at your code when I made my post.
Brian
The algorithm from Phuoc is wrong (beside of a lot of syntax errors)! You cant swap nodes if you only have a next pointer. Consider the case where A->B->C . If swapping B and C, A still is pointing to C what spoils the chain.
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
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
I usually caught same problem as you.
Hi itsmeandnobodyelse !
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.
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.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Hi itsmeandnobodyelse !
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
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
ASKER
ok, so here is my sort code so far. it doesn't work.
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?
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?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
ok, had to add a bracket and the type Term - and it doesnt work, in fact...it just hangs:
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)
{
//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.
ASKER
Got it. The bracket in wrong spot.
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.
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.
ASKER
Now, i am not sure if the instructor doesnt want a swap done (ie he might want the nodes moved around)...
..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??
..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??
Yeah I have debugged and I found my mistake you pointed out.
cur=cur->next; statement is outside the if statement.
Tie is equal, or same.
Non-increasing
A>=B>=C>=D.
Increasing
A>B>C>D.
Tie is "=", Tie is acceptable that means "=" is acceptable.
cur=cur->next; statement is outside the if statement.
Tie is equal, or same.
Non-increasing
A>=B>=C>=D.
Increasing
A>B>C>D.
Tie is "=", Tie is acceptable that means "=" is acceptable.
I am sorry I make a mistake
Non-decreasing:
A>=B>=C>=D
Increasing:
A<B<C<D
Decreasing:
A>B>C>D
Non-decreasing:
A<=B<=C<=D
Non-decreasing:
A>=B>=C>=D
Increasing:
A<B<C<D
Decreasing:
A>B>C>D
Non-decreasing:
A<=B<=C<=D
- 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.