• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
MrChrisnis

Sorting a Linked List

18 posts in this topic

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?
0

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)

[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
}
}
[/code]

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

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
0

Share this post


Link to post
Share on other sites
[quote name='Uzumakis' timestamp='1349979273' post='4989190']
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
[/quote]

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

Share this post


Link to post
Share on other sites
[quote name='Josh Petrie' timestamp='1349982039' post='4989205']
This doesn't address the "sorting" issue at all.
[/quote]
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
0

Share this post


Link to post
Share on other sites
[quote name='Radikalizm' timestamp='1349978942' post='4989187']
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 [url="http://en.wikipedia.org/wiki/Radix_sort"]Radix Sort[/url]
For general purpose sorting you could take a look at [url="http://en.wikipedia.org/wiki/Quicksort"]Quicksort[/url] or [url="http://en.wikipedia.org/wiki/Mergesort"]Mergesort[/url] which are O(n log n) average case solutions which do not sort in-place, or [url="http://en.wikipedia.org/wiki/Heapsort"]Heapsort[/url] which can sort in-place.
[/quote]

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...

[quote name='BeerNutts' timestamp='1349979104' post='4989189']
If you're looking for a more efficient method, then the Sorted list can't be a singly linked list.
[/quote]

+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 "[i]HealthProfile[/i]" class (name it whatever you want, pointing to the [b]node with the next name[/b] and the [b]node with the next health score[/b], 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
1

Share this post


Link to post
Share on other sites
[quote name='Robot Ninja' timestamp='1349988841' post='4989260']
What you should do is sort the data as it's being added to the list.[/quote]

+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.
0

Share this post


Link to post
Share on other sites
[code]
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, " "));
[/code]
STL, f*ck yeah! :P
0

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.
0

Share this post


Link to post
Share on other sites
Sounds like a job for [url="http://en.wikipedia.org/wiki/Merge_sort"]mergesort[/url]. 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!
0

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* [img]http://public.gamedev.net//public/style_emoticons/default/tongue.png[/img]

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
0

Share this post


Link to post
Share on other sites
[quote name='MrChrisnis' timestamp='1350001184' post='4989318']
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?
[/quote]
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.
0

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):
[CODE]
int node_diff(node1, node2) {
int diff = string_diff(node1.name, node2.name);
if (diff == 0)
diff = node1.health - node2.health;
return diff;
}
[/CODE]
where diff < 0 indicates less-than, == 0 for equal-to, and >0 for greater-than. Edited by Felix Ungman
0

Share this post


Link to post
Share on other sites
[quote name='MrChrisnis' timestamp='1350001184' post='4989318']
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?
[/quote]

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.
0

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
0

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 [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

Thanks,
Chris

P.S - I have tried! [img]http://public.gamedev.net//public/style_emoticons/default/sad.png[/img]

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
0

Share this post


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

Enjoy it ;)

[CODE]
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();
}
}
}
[/CODE]

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

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0