Mail Archives: djgpp/1998/04/01/11:45:57
On Wed, 1 Apr 1998, Victor Jetten wrote:
> Hi smart mathematicians,
> I'm displaying a landscape in 3D, made out of quads that do not
> intersect etc. Landscapes tend to be "well behaved", meaning not very
> random with few occlusions. After 3D translation I sort the visible
> polygons on distance with djgpp's quicksort. However, I can "pre-sort"
> the array by assuming the landscape is flat and then make a smart
> indexing so that the polygon farthest away is draw first. This is quick
> and very dirty because obviuously there are height differences. What is
> the fastest method to sort an almost sorted array? Is it still qsort?
> any ideas are very welcome.
For nearly sorted lists both bubble sort and insertion sort perform well.
For large, nearly sorted lists my preference would be for the insertion
sort. To each his own favourite sorting method, but I find the insertion
sort easy to code. The algorithm can be found in any elementary textbook
on data structures and algorithms, but I can post a short code sample if
neccessary.
Elliott Oti
kamer 104, tel (030-253) 2516 (RvG)
http://www.fys.ruu.nl/~oti
- Raw text -