Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

NuffSaid

Rapid sorting of linked-list

This topic is 6086 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

Here''s the problem I''m facing. All my sprites are stored in a linked list. because it is an isometric game, what I''m doing at the moment is going through the list and drawing the sprites with the highest Y coordinate value first, followed by those with lower Y coordinate values. The problem with this approach is that it requires many passes. One way I''ve managed to solve this is to create a seperate linke d-list that does an insertion sort. This brings about 2 major problems.
  • It wastes memory as there is another list in memory
  • It wastes CPU cycles. Objects coordinates are updated every frame, meaning that the second linked list has to be destroyed and recreated each frame. Major problem
Thus, the way I figure I''ll be able to solve this mess is to get rid of the 2nd list and sort the 1st list each frame before rendering begins. Now, apart from an insertion sort (or a bubble sort), I don''t know how else to sort a linked-list. Is there anyway to apply a quicksort to a linked-list? Or is there a better method that I should adopt? Thanks

Share this post


Link to post
Share on other sites
Advertisement
One approach would be to have an array of pointers to you linked list node type. Walk through the linked lists adding them to the array, then quick sort that array.

This means you never actually sort you linked list only the temporary array.

Another approach is when adding to the linked list insert the node at the correct place, but if you change the depth order of the sprite you would have to cut then re-add it.

[The views stated herein do not necessarily represent the view of the company Eurocom ]

Eurocom Entertainment Software
www.Eurocom.co.uk

The Jackal

Share this post


Link to post
Share on other sites
The array approach sounds more plausible than the remove and reinsert method. I might take a look into it, but my original question still stands. Is there a way to apply a quick sort to a linked list?

Share this post


Link to post
Share on other sites
It may also be an idea to adapt your list node insertion code to walk the list and place the node in a sorted position.

Also depending on the operations and how nodes are created you another idea is to put the nodes themselves into a pre-allocated array (aka pool) i.e. if you know that every frame you always have between 80 and 158 nodes per frame rather than using a normal memory allocator, just make an array of nodes with 158 entries - this can (with smallish nodes) do wonders for your cache coherency compared to using malloc/new to allocate nodes.

We do something similar to handle texture changes - although we use multiple lists (all within an array though) one for each unique texture encountered, and also a list of lists for fast lookups.

--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com

Share this post


Link to post
Share on other sites
Nuffsaid,

If you know how many elements are in the linked list (which would be pretty easy), then, yes, you could do a quicksort or merge sort. Just set the high, middle, and low pointers to the right place, and start the algorithm. The implementation would be a bit more complex than using an array, but if you have good list manipulation functions, then it shouldn''t be a big problem.

Nutts

Share this post


Link to post
Share on other sites
You can perform merge sort on a linked list rather easily.. The trick is how you break the list in half. Because it''s a linked list, just taking the first half and the second half isn''t really a good idea. Instead, it''s better to divide the list into elements at even positions and elements at odd positions, mergesort those smaller lists, then join them.

Because I''ve got it sitting around, I''ll post some code for doing that in OCaml.

  
let rec mergeSort lst =
let rec split ls =
match ls with
[] -> ([], [])
| [hd] -> ([hd], [])
| first :: second :: rest ->
let
l1, l2 = split rest
in
(first :: l1, second :: l2)
and merge tup =
match tup with
[], [] -> []
| ls, [] -> ls
| [], ls -> ls
| h1 :: t1, h2 :: t2 ->
if h1 <= h2 then
h1 :: (merge (t1, h2 :: t2))
else
h2 :: (merge (h1 :: t1, t2))
in
match lst with
[] -> []
| [hd] -> [hd]
| _ ->
let
l1, l2 = split lst
in
merge (mergeSort l1, mergeSort l2)
;;


I don''t expect you''ve ever seen any variant of ML before, so that''s probably useless... But it does show that sorting a linked list can be done in place, in O(n lg n) time.

Share this post


Link to post
Share on other sites
I know there is an "optimized" sort for linked lists, because STL provides a container-specific "sort" method for lists, but I don''t know what that method is. Generally, "sort" and "linked list" shouldn''t be mentioned in the same breath. Sounds like you''re trying to have your cake and eat it too. If I were you I''d keep with the two-container method and just eat the memory waste, but it depends on the size of your containers.

Share this post


Link to post
Share on other sites
Just had a look at the STL headers and man, I don''t understand a thing. It is all way too cryptic for me.

I''m using a double linked list, so I presume, using a quicksort isn''t going to be much of a problem(huh?). I''ve got no idea how to do that. I''ll try figure out c_wraith''s code later. Mind is too fuzzy now to do anything...

Thanks a lot for the info.

Share this post


Link to post
Share on other sites
quicksort is a problem in linked lists because in order for quicksort to be efficient, it requires efficient random access to the container. Linked lists--even double-linked lists--have linear random access times, the worst you can get. This is why I said it looked like you''re trying to "have your cake & eat it too": linked lists buy you fast insertion at any point at the cost of slow random access. It''s what we call in the biz a "tradeoff".

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You could keep a fixed size array of pointers to your nodes just make it far bigger then you''ll ever need. Or each node could have multible links (like next1,next2) so that the list could be gone through in two different ways one could be sorted with out fucking up the other.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!