Sorting a Linked List? Help please!

K, so say I create a linked list with 1000 arbitrary float values. What is THE most efficient way to sort from smallest to biggest?

I cant think of a way off hand thats efficient (and wouldn't down the fps by too much).

Any thoughts?

The paper A COMPARATIVE STUDY OF LINKED LIST SORTING ALGORITHMS suggests that the Wegner variation on Quicksort was the fastest tested (see the paper for a C code example,) beaten only by a Tree sort (which "cheated" because it was using a doubly linked list.)

One thing to consider is whether you'll be creating a new list of values to be sorted every time, or re-sorting the previously sorted values which may have changed only a little? Another algorithm may be more efficient if the list is already mostly sorted after the first sort.

By the way, how are you constructing your linked lists? I wrote my own function libraries for linked lists and maps (I calls 'em hashes!) and I'm curious about alternate approaches. :)

Well, the construction of the list is by going through my cloud particles and adding each particle location to the list.

I then need to sort it to find out which is closest to the camera, and thus re-order the zlist of the particles. The partciles locations will be changing every scan (almost every scan), thus it will always be a new list.

Which method would you recommend?

What are you doing with the sorted data? Why do you need to know which is nearest the camera? The GPU should take care of any z sort/blending issues when drawing the particles.

I'd make certain this complicated list work was needed before considering implementations! ;)

Unfortunatly Blitz zordering needs to be re-ordered at times, it isn't handleded by the GPU when

A. the camera changes position in relation to a mesh
B. Your using a custom single surface system that changes the locations of the polygons each scan of the program.

So, i find out what the distance is of each particle to the camera, throw that into a list, and I need to sort the list so I can do a 're-order' of the polygons to get correct alpha effects. Thus, I need to sort a list.

Are you expecting the camera and/or particles to be moving around wildly? If your camera is slowly revolving around a fountain of particles (where particles are moving away from each other at all times), I would expect the previously sorted list to be mostly correct and you may benefit from an algorithm which is good with mostly-sorted lists. If your camera is randomly teleporting every frame around a room with some kind of vortex of particles (which intermingle wildly), you might as well be sorting from scratch every time.



For the initial sort, Quicksort. For latter sorts, probably Quicksort. :)

Quicksort is really really fast. It blows my mind. Try it out - you might find that you don't need to optimize further.



Ouch, that might be slow, what with the square roots and all. If it becomes necessary, you could try using some dirty math to get much faster - but somewhat inaccurate - distances.

Well, he doesn't need to know the actual distance each particle is from the camera - the squared distance will be good enough, so there's no need to use Sqr() at all:

dx# = cam_x# - part_x#
dy# = cam_y# - part_y#
dz# = cam_z# - part_z#
square_dist# = dx*dx + dy*dy + dz*dz

Also, I'm pretty sure that using 2D (X and Z) coords will be good enough for this job, thus speeding things up a bit more:

dx# = cam_x# - part_x#
dz# = cam_z# - part_z#
square_dist# = dx*dx + dz*dz

@octothorpe:
Since the particles are CONSTANTLY being re-arranged (its very random), I will have to resort the list every time, however I can get away with doing it once every 60 frames without anyone noticing.

@big10p:
Those are some great suggestions! I didn't even think about the sqrt thing and the fact that since everything is relative that I dont really need it to be sqrt'ed and just use the base formula for the comparrison. Excellet, that will same me some speed most definately!

Whoa, just tried the 'blitz' version of the quick sort!

OMG...

My sorting (using a linked list manually inserting and doing comparissons) comes to 64 ms for 1000 floats.

The QuickSort does 1000 random floats in 2 ms!

I'm assuming you found this 'Blitz' Quicksort in the Code Archives?

I've gotta say though, 2ms is a lot when you consider 60fps only gives you 16 ms a frame to work with. Plus what level of hardware are you testing on and how does it compare with your minimum requirements? Will that 2 ms be 4-5+ ms only end-users machines?

If you can get away with using it every 60 frames, you'll hav to be careful not to introduce a big performance hit every 60th frame. Is there some way you can work on only a selection of particles each frame and then apply you update every 60th frame? Sorting the whole lot won't happily break down into sorting say every 50 sprites.

I understand your concerns Shifty, but it 'needs' to be done the way it is being done.

@octothorpe:
Nope, ported an example of the c code from the quicksort link you gave me to blitz3d with a few minor optimizations for blitz!

2 ms for 1000 is very good, and is also worst case possiblity. You have to remember that chances of me having more than 1000 cloud particles on the screen is very thin.

Also, 16ms per frame is when your waiting for vsync, so it's wasted time. If I turn the flip wait off and frame limit to 60, then I have an extra 16ms to use at my disposal.

Currently the tests have been pretty good. I can do 1000 cloud particles on the screen at a total of 2ms hit to the system. Now thats:
A. Getting all my particle positions relative to the camera,
B. Coloring the particles and setting up their coordinates
C. factoring in a formation value for the cloud
D. Sending all the particles displayed to a list
E. Sorting the list based on distance from the camera
F. Then going through the final list and ordering the 'quad's in the proper order so not to get alpha artifacts.

The system should be complete with a cloud editor within a week or so. Its very similar to the cloud system used in M$ flight simulator 2005.

The hardware I am testing this on is a 2.4 ghz system, so i can expect the 2 ms to double on half a machine.

I can see your a bit new to blitz there Shifty, I am unsure of your past experiences with game development however I assure you I am well qualified to optimize the system to peak performance. I thank you again for your concerns, however there are simply some things you can't cut corners on (such as sorting quads to keep alpha artifacts out).

:-)

I'm sure you know what you're doing better than I. Not many people don't! Just thinking out loud taking in my old Comp Sci training which wasn't for fun things like computer games. I'm off the (uneducated) opinion that's sorting's not the fastest thing in the world and if it's possible to avoid, avoiding is good. But then if your solution works then kudos, and I'm interested to see the results :D

I don't follow. 1s/60fps = 16.67ms each frames. Vsyncing or not, that's all the time you get if you want to keep your game running at 60fps, and I wouldn't consider it wasted - you're likely going to have a lot more things you're going to want to do per frame unless this is just a cloud demo.

That said, premature optimization is the root of all evil.

@octothorpe:
First off let me answer your 'I don't follow' with 'Vsyncing or not' isn't accurate in your argument. If I vsync, then I could be running at 50 fps, or 65, depending on how my app syncs to the screen vsync (and thus, a wasted 16ms of the system sitting there waiting for the vsync, 16 ms i can't use). So it can be a very speratic 60 fps if I leave vsync on. Turning it off lets me use a guaranteed 16 ms every frame. 16 ms is alot of time with the systems I have been developing (particle systems, tree systems, cloud systems, etc). When I combine worst case with each system i get about 8 ms of time I need to account for (all systems together take about 8ms to process per frame).

True, every ms counts, however you must realize that there are some things that just take time. If the system is completely maxed out (beefed it up to 1000 cloud particles) and it is only costing me 2ms, then so be it....

When it comes to 1000 alphaed cloud particles I have to worry about flip times and fill rates before I have to worry about a 2ms sort and re-order of the zorder of the quads.

2ms in this case is completely acceptable and far better than I had hoped (was expecting around 40 ms, in which case would have thrown the whole project on the back burner till I figured out a better method).



I am not sure I follow...

It's a famous quote attributed to Tony Hoare (incidentally the inventor of the Quicksort algorithm) suggesting that programmers have a tendancy to paint themselves into corners because they try to optimize things before they know where performance bottlenecks are. I was chiding myself.