Solved

Sorting a linked list with bubblesort

Posted on 2006-11-05
5
329 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
0
Comment
Question by:T3rminal
  • 2
  • 2
5 Comments
 
LVL 45

Accepted Solution

by:
Kdo earned 450 total points
ID: 17878229
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
 
LVL 13

Assisted Solution

by:marchent
marchent earned 50 total points
ID: 17878946
   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
 
LVL 45

Expert Comment

by:Kdo
ID: 17881064

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
 
LVL 13

Expert Comment

by:marchent
ID: 17881224
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
 

Author Comment

by:T3rminal
ID: 17883455
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 Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now