• C

Sorting a linked list with bubblesort

Hi,

I'm trying to sort a linear linked list by count from the node below.  Ive tried using a bubble sort but cant seem to get it working, pasted below also, any suggestions would be great.

struct node {
        char string25[26];
        int count;
        struct node * next;
};

After adding some nodes I have a linear list so set curr to head

    curr = head;

    while (head != NULL) {
          head = curr;
          while(head != NULL)   {
          if(curr->count < curr->next->count)
                       curr = curr->next;
          }
          curr = curr->next;
    }

Thanks

T3
T3rminalAsked:
Who is Participating?
 
Kent OlsenConnect With a Mentor Data Warehouse Architect / DBACommented:
Hi T3rminal,

It's hard to see from this snippet exactly what you're doing, but you don't seem to be swapping items.

A true bubble sort finds an item in the wrong place, finds the correct place, and moves the item to that location.  You don't seem to be hunting down the target location.

That said, you'll need to do two relinkings.  When you find a node in the wrong place, the node prior to the ill positioned one must be modified to point to the node after the ill positioned one.  Then the node that you just removed needs to be inserted into the correct place.

  1-> 2 -> 4 -> 5 -> 6 -> 3 -> 7 -> 8 -> 9

Note that '3' is in the wrong place.  To correct this, the pointer at the preceding item (6) must be changed to point to the item after 3 (7).  Then 3 needs to be reinserted.

  Current = Head;
  while (Current & Current->Next)
  {
    if (Current->Count <= Curent->Next->Count)
      continue;

    temp = Current->Next;   // Save a pointer to the item to move
    Current->Next = Current->Next->Next;   // Link past the item in the wrong place.

    Current1 = Head;
    while (Current1->Count < temp->Count)
      Current1 = Current1->Next;

    temp->Next = Current1->Next;
    Current1->Next = temp;
  }


Note that the algorithm isn't complete.  You'll need a bit more code to handle the special case when the item that is being moved becomes the first item in the list.


Good Luck!
Kent
0
 
marchentConnect With a Mentor Commented:
   loop1 = head;
    while (loop1 ->Next != NULL)
    {
          loop2 = loop1->next;
          while(loop2 != NULL)  
          {
                 if(loop1->count < loop2->count)
                         swap(loop1, loop2); //write swap code
                 loop2 = loop2->next;
          }
          loop1 = loop1->next;
    }

~marchent~
0
 
Kent OlsenData Warehouse Architect / DBACommented:

Hi Marchent,

A couple of things about your algorithm.  Well... 4.

-- You've proposed a successive maximum sort.  That's not a bubble sort.
-- The test is backwards (sorts descending instead of ascending)
-- No provision is made for changing the item at head.
-- swap() has no good implementation.  To swap items, you need to pass the node prior to the nodes to swap.

Good try though.  :)

Kent
0
 
marchentCommented:
thanks kdo

ya, it is not a bubble sort. but this is easy for a beginer, even though still i use this sort when number of element is capable to handle.

~marchent~
0
 
T3rminalAuthor Commented:
Hi,

Sorry for the vague first post.  So far I have this but still cant seem to get it working, after enterting the sort I am unable to print anything to screen.  Ultimately I'd just like to sort by count, perhaps bubble sort is not the best method for this?  I didnt think an Insertion Sort would work as its possible I'll have 2 counts which will be the same.

    curr = head;

    while (curr && curr->next) {
          if (curr->count <= curr->next->count)
             continue;
             
          temp = curr->next;
          curr->next = curr->next->next;
         
          curr2 = head;
          while (curr2->count < temp->count)
             curr2 = curr2->next;
         
          temp->next = curr2->next;
          curr2->next = temp;
    }  
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.