• Advertisement
Sign in to follow this  

Sorting a Linked List

This topic is 1925 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey guys,

Right now I am creating a linked list and performing certain functions on it, however I am stuck at one point. I can get the list to display it's elements, however I am trying to figure out how to display the elements in a sorted order.

My list contains objects that contain a name and a health variable. I am trying to sort the name alphabetically, and the health numerically (obviously as separate calls).

I have searched for replies about this on these forums, but knowing nothing about different sorting algorithms myself, it is quite hard to understand what is going on in some of the replies.

Any help that you guys can give, or any "dumbed down" explanations would be great.

Thanks,
Chris

P.S - Would it be better to have a separate Node class that the Object class inherits, or just implement the node functions into the Object class itself?

Share this post


Link to post
Share on other sites
Advertisement
If you want to implement sorting algorithms it's best to make sure you understand them completely so you can be sure they run as intended. It's very easy to make a sorting algorithm very inefficient by not implementing it correctly.

For string sorting you'll want to take a look at Radix Sort
For general purpose sorting you could take a look at Quicksort or Mergesort which are O(n log n) average case solutions which do not sort in-place, or Heapsort which can sort in-place.

Share this post


Link to post
Share on other sites
If you have a singly linked list in random order, the simplest solution would be to generate a 2nd list and insert object in order from the original list. basically this (in pseudo-code)


for each object i in UnsortedList {
for each object j in SortedList {
if i < j {
Insert i in front of j
break
}
}
if not inserted {
Insert i at end of SortedList
}
}


If you're looking for a more efficient method, then the Sorted list can't be a singly linked list.

Share this post


Link to post
Share on other sites
Okay
1st to display out all the elemets in the linked list as you know when you add the list there are basically two portion in the list data containing user data and second portion containing the result of the next node as the last node is null what you need to do is...
suppose
node *start;
node is the basic skelton of the linked list node points to the fist portion
While(start!=NULL){
output the data you wanna get
and after the output
write
start=start->next address of the node;
}
using this you will get the output

Share this post


Link to post
Share on other sites

Okay
1st to display out all the elemets in the linked list as you know when you add the list there are basically two portion in the list data containing user data and second portion containing the result of the next node as the last node is null what you need to do is...
suppose
node *start;
node is the basic skelton of the linked list node points to the fist portion
While(start!=NULL){
output the data you wanna get
and after the output
write
start=start->next address of the node;
}
using this you will get the output


This doesn't address the "sorting" issue at all.

Share this post


Link to post
Share on other sites

This doesn't address the "sorting" issue at all.

i only gave the answer to the first statement of his post for getting the simple output the algo for sorting were posted in the prior post thats why i didnt made any lines on it

Share this post


Link to post
Share on other sites

If you want to implement sorting algorithms it's best to make sure you understand them completely so you can be sure they run as intended. It's very easy to make a sorting algorithm very inefficient by not implementing it correctly.

For string sorting you'll want to take a look at Radix Sort
For general purpose sorting you could take a look at Quicksort or Mergesort which are O(n log n) average case solutions which do not sort in-place, or Heapsort which can sort in-place.


Yes, you should get an understanding of some sorting algorithms first. If you can only use 1 singly linked list, then you would probably have to have functions to sort the names and health and then output it...BUT that's a terrible waste of cycles if you plan on outputting multiple times. What you should do is sort the data as it's being added to the list. So I wonder...


If you're looking for a more efficient method, then the Sorted list can't be a singly linked list.


+1 If you're using a linked list, but aren't restricted how many nodes you can keep track of, then what would be good in your case is if you had two pointers in your "HealthProfile" class (name it whatever you want, pointing to the node with the next name and the node with the next health score, respectively. Technically, the class would contain two singly linked lists inside of it - a double singly-linked list (lol). As you add data to the list, your class should be doing operations on each of those lists to keep them in order. Then when you want to output the names in order, you would iterate through the name nodes, and when you want to output the health scores in order, then you would iterate through the health nodes. Please let me know if you need clarification. I explain things in a confusing way sometimes, but it makes sense to me.

*EDIT* Sorry I used the term "pointer". C++ is my primary language, and I don't know what you work with. Edited by Robot Ninja

Share this post


Link to post
Share on other sites

What you should do is sort the data as it's being added to the list.


+1 for this.

But assuming that you must sort, be aware that classic sort routines are for vectors, not linked lists. One way of sorting a linked list is to build a new one; declare a new head node, walk through your list, for each item remove it and add it to the appropriate place in the new list.

Another way is to sort it into a binary tree, but of course the sorted result won't be a linked list anymore.

Share this post


Link to post
Share on other sites

std::list<int> foo(100);
std::generate(foo.begin(), foo.end(), std::rand);
foo.sort();
std::copy(foo.begin(), foo.end(), std::ostream_iterator<int>(std::cout, " "));

STL, f*ck yeah! :P

Share this post


Link to post
Share on other sites
I think the best way to sort a linked list without copying into a vector, is to use merge sort, which will be O(n log n) even on a linked list, I believe (Right?).

The easiest way to implement merge sort is recursively and depending your requirements the recursive implementation is probably fine; however, if you need sort really really big lists doing it recursively may be a bad idea.

Share this post


Link to post
Share on other sites
Thanks for all the replies so far guys. Taking a little break because I've been staring at this stuff for a while now and it's just like *boom, head explode* tongue.png

My list relies on the user adding the data in themselves, therefore there is nothing in the list to start with, so would it be better for me to amend my add/add_to_end functions to sort the objects as they are added in? Edited by MrChrisnis

Share this post


Link to post
Share on other sites

My list replies on the user adding the data in themselves, so would it be better for me to amend my add/add_to_end functions to sort the objects as they are added in?

That would be simpler. If you need to sort multiple times (that is, if you have multiple lists you want to sort), then writing a sort function that can be reused would make sense. But I'd go with what you suggested there if that's all you need to do.

Share this post


Link to post
Share on other sites
Whatever language you are using there should be a standard library for sorting stuff so that you don't have to write your own.

As for sorting on multiple attributes, the best way is to do it in one call but use a compare function like this (pseudocode):

int node_diff(node1, node2) {
int diff = string_diff(node1.name, node2.name);
if (diff == 0)
diff = node1.health - node2.health;
return diff;
}

where diff < 0 indicates less-than, == 0 for equal-to, and >0 for greater-than. Edited by Felix Ungman

Share this post


Link to post
Share on other sites

My list relies on the user adding the data in themselves, therefore there is nothing in the list to start with, so would it be better for me to amend my add/add_to_end functions to sort the objects as they are added in?


In this case, you should consider storing the data in a binary search tree instead of a linked list because if you insert into a binary search tree you get sorted-ness for free. I don't know what language you are working in but in C++ i'm talking about using either an std::set or an std::map.

However, i don't know what you are doing so it might make sense to use a linked list maintained as ordered if you actually need list functionality such as O(1) unordered inserts or O(1) splicing of two lists together, etc.

Share this post


Link to post
Share on other sites
Optimizing (if the circumstances allow it)

If the data DOESNT change as much as the sorted list gets displayed, then retaining the Sort results data between its use (only resorting when the list changes).

Then it might even be possible to optimize by extracting each individual changed item from the Sort data and re-insert it into that previous Sort-Result (eliminating a full/complete resort every time) -- only if a few change.

For data sets that the majority of data constantly change, you will have to rebuild the sorted results every time you used them (display them)

----

Another consideration for the actual Sort methodology is how big is the set of items being sorted. Some more complicated Sort methodology (which may be efficient for large data sets) may have alot of overhead as compared to a simpler more brute-force Sort done on a small set. Sometimes you can even check the data set size at run-time and have a decision made between two methods (after having off-line tested to see where the crossover point is with typical data set size ranges)

----

I would use a Binary Tree Sort for large random data sets (the sorted tree data is seperate from the 'link list' so can be a different data type - though I have frequently had both the link list chain data AND seperate tree Sort data elements in the objects 'record' struct.

More esoteric :

For some huge data sets, cache hit/collision issues with some sorts become important for game speed and you want the Sort manipulation data to be as tiny as possible (possibly one of those "Structure of Arrays" kind of things for permanent object data) Edited by wodinoneeye

Share this post


Link to post
Share on other sites
Okay, I've tried implementing my own insertion sorting after writing it out, and it is still confusing me. This causes the program to pretty much break after one Beast has been inserted into the list. It doesn't break out or crash or anything like that, it just stops outputting the command line requests that it is supposed to and stop allowing the user to enter in any more inputs.

If you guys could look through it and give me some hints on how I can fix this it would be great smile.png

Thanks,
Chris

P.S - I have tried! sad.png

EDIT: My code is displaying in this post as though it is on one long line. I am not sure how to fix this or if it is showing like this for other people so I am sorry if it is Edited by MrChrisnis

Share this post


Link to post
Share on other sites
Looks like it's because of line endings.

Enjoy it ;)


void SimpleLinkedList::add_numerical(Beast *b)
{
if(head == NULL)
{
head = b;
return;
}
Beast *previous = head;
Beast *next = previous->get_next();
while(next != NULL)
{
if(head->get_HP() < b->get_HP())
{
next = head;
head = b;
b->set_next(next);
}
if(next->get_HP() get_HP()) -- //wtf?
{
previous->set_next(b);
next = next->get_next();
}
if(next->get_HP() > b->get_HP())
{
next = next->get_next();
}
}
}


I suggest you to write abstract Linked list such it's in STL and then inherits custom list of it.

Share this post


Link to post
Share on other sites
Hmm, that mistake isn't in my code =S

Copy and paste fail ftw.

I fixed the problem I had (Needed a return call added after b->set_next(next); in the first if statement), and have run into another. Time to go try to figure that out.

And I have to do it this way as it is an assignment that I am working on and my lecturer wants it done this way :(

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement