Archived

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

Promit

Extremely fast, imperfect sort?

Recommended Posts

Are there any sorting algorithms which run extremely fast and don''t necessarily return a perfectly sorted set, merely a mostly sorted set? I''m mainly interested in it for Z-sorting faces, and I don''t think any of the sort algos I know (quick, insertion, selection, heap, merge, etc.) are really right for the job. Is there a faster algorithm I can make use of, given that the results have to be only an approximately sorted set?

Share this post


Link to post
Share on other sites
An abbreviated shell sort might fit the bill. Alternately a quick sort terminated at a certain subsize without the final insertion sort pass might work. How many items are we talking about here anyways?

Share this post


Link to post
Share on other sites
Run one or two passes of bubblesort. If the sort is run every frame, then any unsortednesses will sort themselves out in a few frames. (very punny )

Share this post


Link to post
Share on other sites
bubble will be far too slow and strenuous on the stack.

consider Radix, very very fast(in fact, nearly free if you can
remove the loop - which is possible in rendering engines) and
you can limit the sorted-ness based on the significant figure
you want eg. only sort by the 2nd & 3rd sig. figure.

its very simple to implement as well.

only drawback that i have encounterd is that it only sorts
UNSIGNED integer values (and floats but that could get
messy)

as far as i know it works for strings/floats/word/uint/dword
values.

contact me via e-mail if you need any help
silvermace007#hotmail

FORMAT: wrong e-mail addy

[edited by - silvermace on March 19, 2004 11:14:43 PM]

Share this post


Link to post
Share on other sites
I use the radix sort given in the article above and it works great for all my sorting needs, including transparent object z-sorting.

Share this post


Link to post
Share on other sites