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

on
Medium Priority
351 Views
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

if(curr->count < curr->next->count)
curr = curr->next;
}
curr = curr->next;
}

Thanks

T3
Comment
Watch Question

## View Solutions Only

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.

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.

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.

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

Commented:

Hi Marchent,

-- You've proposed a successive maximum sort.  That's not a bubble sort.
-- The test is backwards (sorts descending instead of ascending)
-- 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~

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.

while (curr && curr->next) {
if (curr->count <= curr->next->count)
continue;

temp = curr->next;
curr->next = curr->next->next;

while (curr2->count < temp->count)
curr2 = curr2->next;

temp->next = curr2->next;
curr2->next = temp;
}
##### Thanks for using Experts Exchange.

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