Newsgroups: comp.os.msdos.djgpp
From: Elliott Oti <oti AT fys DOT ruu DOT nl>
Subject: Re: fastest sort for an almost sorted array?
Sender: usenet AT fys DOT ruu DOT nl (News system Tijgertje)
Message-ID: <Pine.OSF.3.95.980401144120.318A-100000@ruunat.fys.ruu.nl>
In-Reply-To: <35223233.53AD6263@frw.ruu.nl>
Date: Wed, 1 Apr 1998 13:02:08 GMT
Reply-To: Elliott Oti <oti AT fys DOT ruu DOT nl>
Content-Type: TEXT/PLAIN; charset=US-ASCII
References: <35223233 DOT 53AD6263 AT frw DOT ruu DOT nl>
Mime-Version: 1.0
Organization: Physics and Astronomy, University of Utrecht, The Netherlands
Lines: 27
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

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