Message-ID: <32997393.2FEF@pobox.oleane.com>
Date: Mon, 25 Nov 1996 11:23:15 +0100
From: Francois Charton <deef AT pobox DOT oleane DOT com>
Organization: CCMSA
MIME-Version: 1.0
To: "Brennan The Rev. Bas Underwood" <brennan AT mack DOT rt66 DOT com>
CC: djgpp AT delorie DOT com
Subject: QuickSort [Was: Re: GDB debugging]
References: <579aaf$l6k AT isnews DOT csc DOT calpoly DOT edu> <57beeg$iaa AT mack DOT rt66 DOT com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

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