• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 432
  • Last Modified:

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 :)
0
bingie
Asked:
bingie
  • 8
  • 4
  • 3
  • +2
2 Solutions
 
brettmjohnsonCommented:
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
 
phuocnhCommented:
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);
0
 
BrianGEFF719Commented:
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
BrianGEFF719Commented:
Btw, the methoed I mentioned is effectivly a bubble sort algorithm :)
0
 
phuocnhCommented:
Hi BrianGEFF719,
Yours are same as my post!
Phuoc H. Nguyen
0
 
BrianGEFF719Commented:
phuocnh,
You're right...sorry about that, I didn't look at your code when I made my post.


Brian
0
 
itsmeandnobodyelseCommented:
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
 
phuocnhCommented:
I usually caught same problem as you.
0
 
phuocnhCommented:
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.
0
 
itsmeandnobodyelseCommented:
>>>> What is syntax error?

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


0
 
phuocnhCommented:
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
 
bingieAuthor Commented:
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->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
 
phuocnhCommented:
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.
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.
0
 
bingieAuthor Commented:
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.
0
 
bingieAuthor Commented:
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.
0
 
bingieAuthor Commented:
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
 
phuocnhCommented:
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
 
phuocnhCommented:
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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 8
  • 4
  • 3
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now