[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-freeqt
Subject:    Re: [freeqt] QVector
From:       Andrew J Bromage <Andrew.Bromage () its ! monash ! edu ! au>
Date:       2000-08-20 5:20:55
[Download RAW message or body]

G'day all.

On Fri, Aug 18, 2000 at 10:16:43AM +0100, Nick Huxley wrote:

> Really these classes should all have two sort options qsort for overall
> speed and heapsort for stability.

Heapsort isn't stable.  It doesn't preserve order in the case of
equivalent keys.

> Heapsort is an in place sort that isn't
> as fast as qsort on average but never goes above a certain complexity at
> the worst case. Qsort has a worse case of N^2!! This is very important when
> the longest possible time must never occur. QT has to my knowledge only the
> qsort which is a poor decision IMHO. The STL has both.

The STL also has an in-place merge sort which has the same complexity
but much lower constant factors than heapsort.  You might want to
consider using something like that.

> Looking through the sort code sent to me there  is also the problem of
> stupid global macros which are needed in C but not C++.

Of course.  However, you asked for LGPL'd quick sort code. :-)

Cheers,
Andrew Bromage

[prev in list] [next in list] [prev in thread] [next in thread]