We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

Sorting a linked list with bubblesort

T3rminal
T3rminal asked
on
Medium Priority
351 Views
Last Modified: 2010-04-15
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
Comment
Watch Question

Data Warehouse / Database Architect
CERTIFIED EXPERT
Commented:
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

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
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~
Kent OlsenData Warehouse / Database Architect
CERTIFIED EXPERT

Commented:

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

Commented:
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~

Author

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;
    }  
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.