Mail Archives: djgpp/1996/11/25/05:46:37
Brennan The Rev. Bas Underwood wrote:
>
> In article <579aaf$l6k AT isnews DOT csc DOT calpoly DOT edu>,
> Aaron Dwyer <adwyer AT galaxy DOT csc DOT calpoly DOT edu> wrote:
> > I'm currently finishing up an implementation of quicksort in DJGPP to
> >sort polygons far to near, classic painter's algo situation...BUT...my
> [snip]
>
> Try using the libc qsort() function to prototype first. It's a pretty
> good implementation. I had all these ideas for optimizing my sorting
> until I profiled my program... qsort (and components) took less than 2%
> of the time.
>
If you are using quicksort, another reason might be that you try to sort
(almost) already sorted tables :
Quicksort is a very fast algorithm *on average*, which can be very slow
(ie o(n*n)) in some rare occasions : one of them being when the data is
already (almost) sorted.
This is rare enough not to bother in most applications, but it can happen
1/ "on purpose" when you use Quicksort "just in case" (the data should be
sorted, but let's check again...).
2/ unintentionnaly, if your program *needs* to sort large arrays which
often happen to be almost already sorted. (this can happen in algorithms
where the data to be sorted are already partially sorted by some previous
algorithm...)
In such cases, improving the coding of quicksort won't help, the problem
is with the algorithm, not its implementation.
To workaround, try using "heapsort", a true o(nlog(n)) algorithm. A
description and an implementation of it can be found in Numerical Recipes
in C (W. Press et al, Cambridge University Press)
Francois
- Raw text -