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

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
0
T3rminal
Asked:
T3rminal
  • 2
  • 2
2 Solutions
 
Kent OlsenData 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
 
marchentCommented:
   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

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

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