Jump to content

  • Log In with Google      Sign In   
  • Create Account


Sorting a Linked List


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
18 replies to this topic

#1 MrChrisnis   Members   -  Reputation: 340

Like
0Likes
Like

Posted 11 October 2012 - 11:44 AM

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?

Sponsor:

#2 Radikalizm   Crossbones+   -  Reputation: 2776

Like
4Likes
Like

Posted 11 October 2012 - 12:09 PM

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.

I gets all your texture budgets!


#3 BeerNutts   Crossbones+   -  Reputation: 2572

Like
0Likes
Like

Posted 11 October 2012 - 12:11 PM

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.
My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

#4 Uzumakis   Members   -  Reputation: 130

Like
0Likes
Like

Posted 11 October 2012 - 12:14 PM

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

#5 Josh Petrie   Moderators   -  Reputation: 2955

Like
0Likes
Like

Posted 11 October 2012 - 01:00 PM

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.

Josh Petrie | Core Tools Engineer, 343i | Microsoft C++ MVP


#6 Uzumakis   Members   -  Reputation: 130

Like
0Likes
Like

Posted 11 October 2012 - 01:17 PM

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

#7 Robot Ninja   Members   -  Reputation: 569

Like
1Likes
Like

Posted 11 October 2012 - 02:54 PM

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, 11 October 2012 - 02:55 PM.


#8 mhagain   Crossbones+   -  Reputation: 7462

Like
0Likes
Like

Posted 11 October 2012 - 03:27 PM

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.

It appears that the gentleman thought C++ was extremely difficult and he was overjoyed that the machine was absorbing it; he understood that good C++ is difficult but the best C++ is well-nigh unintelligible.


#9 japro   Members   -  Reputation: 887

Like
0Likes
Like

Posted 11 October 2012 - 04:23 PM

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

#10 jwezorek   Crossbones+   -  Reputation: 1640

Like
0Likes
Like

Posted 11 October 2012 - 05:01 PM

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.

#11 Shaquil   Members   -  Reputation: 815

Like
0Likes
Like

Posted 11 October 2012 - 05:52 PM

Sounds like a job for mergesort. You'll learn a lot about sorting algorithms just from studying one at a time. You've stumbled into an interesting area of computer science. Have fun!

#12 MrChrisnis   Members   -  Reputation: 340

Like
0Likes
Like

Posted 11 October 2012 - 06:19 PM

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* Posted Image

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, 11 October 2012 - 08:41 PM.


#13 Cornstalks   Crossbones+   -  Reputation: 6966

Like
0Likes
Like

Posted 11 October 2012 - 08:32 PM

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.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#14 Felix Ungman   Members   -  Reputation: 920

Like
0Likes
Like

Posted 12 October 2012 - 12:34 AM

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, 12 October 2012 - 12:35 AM.

openwar  - the real-time tactical war-game platform


#15 jwezorek   Crossbones+   -  Reputation: 1640

Like
0Likes
Like

Posted 12 October 2012 - 12:44 AM

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.

#16 wodinoneeye   Members   -  Reputation: 679

Like
0Likes
Like

Posted 12 October 2012 - 07:02 PM

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, 12 October 2012 - 07:09 PM.

--------------------------------------------Ratings are Opinion, not Fact

#17 MrChrisnis   Members   -  Reputation: 340

Like
0Likes
Like

Posted 14 October 2012 - 01:47 PM

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 Posted Image

Thanks,
Chris

P.S - I have tried! Posted Image

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, 19 October 2012 - 08:01 AM.


#18 AlexB.hpp   Members   -  Reputation: 201

Like
0Likes
Like

Posted 14 October 2012 - 04:10 PM

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.
C x 2 C x o C x C f nice C x C s C x C c

#19 MrChrisnis   Members   -  Reputation: 340

Like
0Likes
Like

Posted 14 October 2012 - 04:14 PM

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 :(




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS