Solved

# Sorting...

Posted on 2006-05-23
429 Views
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:

if (cur->item < cur->next->item){
//do nothing
}
else{
}

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 :)
0
Question by:bingie

LVL 23

Expert Comment

2 Hints:
- 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.

0

LVL 6

Expert Comment

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
{
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;
{
}
//There is till a swapping.
Done=FALSE;
}//if
else
{
cur=cur->next;
}//else
}//do-while
while (Done ==FALSE);
0

LVL 19

Expert Comment

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
0

LVL 19

Expert Comment

Btw, the methoed I mentioned is effectivly a bubble sort algorithm :)
0

LVL 6

Expert Comment

Hi BrianGEFF719,
Yours are same as my post!
Phuoc H. Nguyen
0

LVL 19

Expert Comment

phuocnh,

Brian
0

LVL 39

Expert Comment

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
0

LVL 6

Expert Comment

I usually caught same problem as you.
0

LVL 6

Expert Comment

Hi itsmeandnobodyelse !
What is syntax error?
I use temp variable to store pointer so I cannot lose the link.
I fix my code now:
(BubbleSort)
boolean Done;
{
//if list is not empty, sort it.
do
{
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.
0

LVL 39

Assisted Solution

>>>> What is syntax error?

1.
boolean Done;  // bool Done

2.

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

0

LVL 6

Expert Comment

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

0

LVL 11

Author Comment

ok, so here is my sort code so far. it doesn't work.

bool sortYes = false;

do
{      sortYes = false;

for (placeholder1; placeholder1 !=NULL; placeholder1 = placeholder1->next){
for (placeholder2; placeholder2 != NULL; placeholder2=placeholder2->next){
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?
0

LVL 6

Accepted Solution

Why don't you read my latest code post above. I have compile and test it.
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.
A->B->C.
When you swap B and C. A->next->B not C so you lose the list.

{
//if list is not empty, sort it.
do
{
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.
0

LVL 11

Author Comment

ok, had to add a bracket and the type Term - and it doesnt work, in fact...it just hangs:

bool Done;

{
//if list is not empty, sort it.
do
{
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.
0

LVL 11

Author Comment

Got it. The bracket in wrong spot.

bool Done;

{
//if list is not empty, sort it.
do
{
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.
0

LVL 11

Author Comment

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??
0

LVL 6

Expert Comment

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.
0

LVL 6

Expert Comment

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
0

## Featured Post

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. â€¦
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article locâ€¦
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.