[Nice implementation of quicksort elided.]
Quicksort is probably the most studied single algorithm ever developed.
There's a whole, high-quality PhD dissertation on it (I think Robert
Sedgewick's.  He later published a book on sorting algorithms.)

Stubbs's implementation is pretty close to the state of the art - which
was established 10+ years ago, but still seems to be terra incognita to
most implementers of quicksort.  In fact, you can still find recent,
allegedly professional, implementations that choose the first, or the
last, element of the subfile as the pivot - despite that fact that
Hoare's original paper, in the early '60's, pointed out the dangers of
this approach and recommended against it!  The improvement from the
"middle of three" approach was recognized very early on - and the
importance of actually sorting the three chosen elements is discussed in
Knuth - even in the first edition - among other places.

As Stubbs points out, the vast bulk of the time in quicksort is spent in
the inner loop.  The quality of a quicksort implementation is determined
by the care and feeding of that inner loop.  If set up properly, the
inner loop should be no more than a couple of instructions long.  I
think it was Sedgewick who observed that Quicksort made a good test of a
compiler's optimization pass:  The performance that you *should* be able
to get out of quicksort on a given machine can be calculated with fairly
good precision.  Compile up a good quicksort implementation and see if
you get close....  Apparently, there have in the past been optimizers
that made the inner loop *slower*.  In practice, for production use,
it's worth looking at the code generated for the inner loops ... you may
be surprised.

I would make two suggestions to speed up Stubbs's implementation (though
how much of a change they'd produce is hard to say):

1.  Using some alternative method for partitioning "small" subfiles is
essential, as Stubbs notes.  Mergesort is a good choice, but one can
perhaps do better with a trick (not due to me!).  Suppose, when you got
to a "small" subfile, you simply ignored it.  Then, when the quicksort
was finished, you'd have a file that was globally "close to sorted" but
might have some local deviations from the sort order.  (Using Stubbs's
cutoff of 15 elements for a "small" subfile, no element could be more
than 14 positions away from where it belongs.  Now do a single bubble
sort - actually, for this application "cocktail-shaker sort", which
bubbles in both directions, or other similar variations that amount to
insertion sorts - over the entire file.  We know that bubble sort is
very bad in general, but in this case we know that no element has to
move very far - and that's what determines how long these "dumb" sorts
take.

The advantage of the single pass is that it avoids paying the cost of
setting up the "dumb" sort repeatedly.  The reason one has to handle
small subfiles separately is that, by their very nature, there are
plenty of them - so after making the inner loop of quicksort as fast as
possible, the next hot spot (down by an order of magnitude or more,
granted) is small subfile sorting.  (Modern machines *have* changed the
tradeoff a bit:  If you do the small subfile sorting immediately,
there's a chance that many of the elements will already be in the cache.
Only careful experimentation can determine if this effect is signficant
enough to make a difference.  While it's possible to produce a really
good portable sorter, for the absolute best performance, some tuning is
still needed for each particular implementation.  Whether it actually
*matters* is a different question....)

2.  Stubbs uses the system rand() function to pick a partitioning
element.  rand() is not a very good random number generator, and can be
surprisingly expensive on some hardware.  It's probably better to do
your own random number generation in-line in the code.  (In another,
similar kind of application, I use a "multiply-with-carry" generator
George Marsaglia posted a while back:

 static unsigned long z=362436069, w=521288629;
 void setseed(unsigned long i1,unsigned long i2){z=i1; w=i2;}

 #define znew  ((z=36969*(z&65535)+(z>>16))<<16)
 #define wnew  ((w=18000*(w&65535)+(w>>16))&65535)
 #define IUNI  (znew+wnew)

(32-bit arithmetic assumed.)  IUNI is a random 32-bit unsigned value.
According to Marsaglia, this generator passes all the widely-used test
for PRNG (see http://stat.fsu.edu/pub/diehard/cdrom) - but for this
application, it hardly matters.  There are also cheap ways to pick a
number in a given range - cheaper than using FP arithmetic or  integer
division - which may be a bit more biased than the best approaches, but
in practical use for sorting should do just fine.

Again, how much this might matter is impossible to know without some
experimentation.  Since one random number is drawn per subfile, it might
be significant.  (On the other hand, no random numbers are needed for
"small" subfiles, and there are many fewer "large" subfiles.)

       -- Jerry


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <01bda43c$1b8c1440$8a1ec2d0@porky>,
  "P.J. Plauger" <pjp@dinkumware.com> wrote:
> Uh, I don't see how is the *median* of three elements different if you sort
the
> elements and take the middle one or if you evaluate the template function:
>
>   // TEMPLATE FUNCTION _Median
> template<class _Ty> inline
>  _Ty _Median(_Ty _X, _Ty _Y, _Ty _Z)
>   {if (_X < _Y)
>    return (_Y < _Z ? _Y : _X < _Z ? _Z : _X);
>   else
>    return (_X < _Z ? _X : _Y < _Z ? _Z : _Y); }
>
> The above is taken from <algorithm> as shipped with VC++ V5.0. Am I missing
> something?

The _first_ pass through the array results in the same median either way.  But
by rearranging the first, middle, and last elements in order while computing
the median, _subsequent_ passes end up picking a different median.  For this
particular input sequence, it happens to make all the difference.

I suspect that this rearranging of elements causes the overall quicksort to
degenerate to quadratic on fewer input sequences, but I have no proof -- I
just have the one example I gave.  It's certainly worthy of investigation,
wouldn't you agree?  (Although introsort makes it much less important.)


-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

gtalvola@parlance-ncs.com wrote in article <6nau9i$uih$1@nnrp1.dejanews.com>...
> >  Incidentally, offhand I don't think that "sort[ing] the three elements
> > in place" affects this at all. You still get the same bad pivot element,
> > and you still get the same highly unequal partitions. You sort the three
> > elements in order to be able to choose the median.
>
> It actually does solve the problem, because sorting those 3 elements prevents
> the bad pivot from being selected on the next pass.  Here's sample code to
> prove it, containing first the quicksort implementation as implemented in VC++
> 5.0, and then my fixed version which sorts the 3 elements as it picks the
> median.

Ah, thanks. I missed that part. It's not just the business of picking the
median that matters, but the rearranging of future candidates. Good point.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35993018.CD143C79@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
>
>  "Doctor, it hurts when I do this." "So don't do that."
>  Making the behavior change is not the same as solving the problem.
> Reread the part of my message that you snipped. When you push a problem
> away from one sort of input sequence you push it onto another. The fact
> that it's out of your way in your particular example does not mean there
> was anything wrong with the initial implementation, or that the version
> that works better with your input is better in the general case. In
> fact, I'll bet that the user whose data sorts in N^2 with your version
> but logN with the initial one will be very unhappy with your version.

I understand that I haven't proven anything general with my one specific
example.  However, it's not necessarily the case that "when you push a
problem away from one sort of input sequence you push it onto another."  Some
heuristics are better than others.  It could very well be (but I have no
proof) that the version I posted has many fewer (or possibly many more)
degenerate input sequences than the original version.  It's worth
investigating.

> Why is it "significantly less likely"? If you're randomly choosing
> numbers from 1 to 20 those two sequences will occur with exactly the
> same probability. If you're relying on special knowledge of a particular
> problem domain, you may be right. But we're talking about general
> purpose algorithms here, not algorithms tuned for a particular type of
> input data.

I meant that it is significantly less likely in practice, where you often are
not sorting random sequences.  A general-purpose algorithm should be
resilient to common types of input -- after all, that's why median-of-three
was invented. An already sorted sequence with an extra element added to the
end is probably fairly common in practice, while the other sequence suggested
in David Musser's article seems much less likely to occur in practice.

>  Further, it's important to be able to explain to people what they need
> to watch out for when they use a sorting algorithm. If the second
> example is a typical problem case, it's easy: "don't use quicksort with
> nearly ordered data." How would you describe the first sequence, in
> order to avoid setting a trap for users?

There is no easy way to describe the first sequence -- it is a carefully
contrived sequence to foil median-of-three quicksort.  I doubt that anyone
has actually run into it in a practical application of quicksort.  And I
would submit that any algorithm for which you have to avoid using nearly
ordered data should not be used as a general-purpose sorting algorithm, which
is what std::sort is.  I don't think anything in the C++ standard states that
you should avoid std::sort on nearly ordered sequences, yet that is what I
have to do with my available std::sort implementation.


- Geoff Talvola
  gtalvola@parlance-ncs.com

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6nbo39$6gv$1@nnrp1.dejanews.com>,
  gtalvola@parlance-ncs.com wrote:

> I meant that it is significantly less likely in practice, where you often are
> not sorting random sequences.  A general-purpose algorithm should be
> resilient to common types of input -- after all, that's why median-of-three
> was invented. An already sorted sequence with an extra element added to the
> end is probably fairly common in practice, while the other sequence suggested
> in David Musser's article seems much less likely to occur in practice.

Two points:

1. Your comments are interesting.  I'm used to seeing already sorted and
reverse sorted as special test cases, and one generally tests the pivot
to make sure it isn't bad for these.  I've never read of using already
sorted, plus an element appended, but I think that you're right, and it
probably is a good idea.

2. In general, of course, when inserting in a sorted array, you don't
simply append, then resort, but rather use an insertion routine, which
scans back until it finds the location, then inserts.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
        +49 (0)69 66 45 33 10    mailto: jkanze@otelo.ibmmail.com
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orientee objet --
              -- Beratung in objektorientierter Datenverarbeitung

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 30 Jun 1998 18:55:56 GMT, Pete Becker <petebecker@acm.org> wrote:

> Further, it's important to be able to explain to people what they need
>to watch out for when they use a sorting algorithm. If the second
>example is a typical problem case, it's easy: "don't use quicksort with
>nearly ordered data." How would you describe the first sequence, in
>order to avoid setting a trap for users?

"If you need guaranteed N log N performance for all input sequences,
don't use quicksort. If you know enough about your input sequences to
know that quicksort will have bad performance, you should probably be
using an algorithm tuned specifically for those sequences. If you
don't but can't tolerate bad worst-case times, you should use an
algorithm with guaranteed performance for all sequences."

For quite a few years the standard choice was quicksort for fastest
average performance, heapsort for guaranteed worst-case and not much
worse average. More recent developments may change that, but both
quicksort and heapsort are easily available to users of most standard
library implementations, so that's still going to be the obvious
choice for many users.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

gtalvola@parlance-ncs.com wrote:
>
> I didn't have to work hard to find the sequence -- it arose naturally in the
> course of my work.  And from all that I've read about it, median-of-three
> quicksort is supposed to be very robust to a wide variety of input sequences,
> so I was very surprised to see quadratic behavior.
>

 Median of three is a heuristic, not an absolute solution. The
underlying problem is that quicksort does badly when it chooses pivot
values that are close to the ends of the range that it is sorting.
Unless you eliminate this possibility (choosing from a larger group of
potential pivot elements can improve the partitioning, but at the cost
of making pivot selection more costly), there is always a sequence that
generates the worst case, and if you want to, you can work out a
sequence that gives you that worst case for yourself. Look at the range
of values, pick one of the worst possible pivot values (the second
largest or the second smallest will work well), and arrange the sequence
so that the pivot selection technique (whichever variant you prefer)
will select it. That only requires setting the positions of three
elements. Do the partition. Then repeat the process on the larger of the
two new partitions. Continue until done. Then work your way upwards,
undoing all of the partitioning and making sure that you're putting the
bad pivot in the "right" place each time. You'll end up with your
initial data in an order that produces N^2 time. Want to try a different
variation of median-of-three? Then do the exercise again. You'll end up,
again, with an ordering for your initial data that produces N^2 time.
Median-of-three is "better" than simply choosing a single value because
it makes this worst case less likely to occur, and it makes it a bit
less severe when it does occur (you end up with partitions of two
elements instead of 1). It does not, and cannot, eliminate it.
 Incidentally, offhand I don't think that "sort[ing] the three elements
in place" affects this at all. You still get the same bad pivot element,
and you still get the same highly unequal partitions. You sort the three
elements in order to be able to choose the median.
--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <359862D7.2067328A@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:

>  Incidentally, offhand I don't think that "sort[ing] the three elements
> in place" affects this at all. You still get the same bad pivot element,
> and you still get the same highly unequal partitions. You sort the three
> elements in order to be able to choose the median.

It actually does solve the problem, because sorting those 3 elements prevents
the bad pivot from being selected on the next pass.  Here's sample code to
prove it, containing first the quicksort implementation as implemented in VC++
5.0, and then my fixed version which sorts the 3 elements as it picks the
median.

This fixed version of median-of-three certainly does not _prevent_ quadratic
behavior.  But the sequences that cause quadratic behavior are much less
likely to arise in practice.  For example, according to David Musser's
article "Introspective Sorting and Selection Algorithms", sequences like

1 11 3 13 5 15 7 17 9 19 2 4 6 8 10 12 14 16 18 20

will cause quadratic behavior even with the fixed median-of-three.  Still,
this is signficantly less likely to arise in practice than the sequence I ran
into:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1


/////////////////////////////////////////////////////////////////
// This program produced the following output:
//
// ordering vector in a special way...
// calling broken::quicksort on the vector...
// number of comparisons: 50074820
// number of assignments: 29985
// number of copy constructions: 59940
// sorted!
//
// randomly shuffling vector...
// calling broken::quicksort on the vector...
// number of comparisons: 158786
// number of assignments: 82500
// number of copy constructions: 38026
// sorted!
//
//
// ordering vector in a special way...
// calling fixed::quicksort on the vector...
// number of comparisons: 207004
// number of assignments: 22557
// number of copy constructions: 14106
// sorted!
//
// randomly shuffling vector...
// calling fixed::quicksort on the vector...
// number of comparisons: 153502
// number of assignments: 82600
// number of copy constructions: 34654
// sorted!
//
//
/////////////////////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>

struct Integer {
    Integer(): value(0) {}
    Integer( int i ): value(i) {}
    Integer( const Integer& i )
        : value(i.value)
    {
        ++num_copy_constructions;
    }

    bool operator<( const Integer& I ) const
    {
        ++num_comparisons;
        return value<I.value;
    }

    void operator=( const Integer& I )
    {
        ++num_assignments;
        value = I.value;
    }

    int value;


    static void ReportStats()
    {
        std::cout << "number of comparisons: "
                  << num_comparisons << std::endl;
        std::cout << "number of assignments: "
                  << num_assignments << std::endl;
        std::cout << "number of copy constructions: "
                  << num_copy_constructions << std::endl;
        ClearStats();
    }
    static void ClearStats()
    {
        num_comparisons = 0;
        num_assignments = 0;
        num_copy_constructions = 0;
    }
    static int num_comparisons;
    static int num_assignments;
    static int num_copy_constructions;
};

int Integer::num_comparisons = 0;
int Integer::num_assignments = 0;
int Integer::num_copy_constructions = 0;

namespace broken {
template<class _Ty> inline
    _Ty _Median(_Ty _X, _Ty _Y, _Ty _Z)
        {if (_X < _Y)
            return (_Y < _Z ? _Y : _X < _Z ? _Z : _X);
        else
            return (_X < _Z ? _X : _Y < _Z ? _Z : _Y); }
template<class _RI, class _Ty> inline
    void _Sort(_RI _F, _RI _L, _Ty *)
    {for (; std::_SORT_MAX < _L - _F; )
        {_RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),
            _Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1))));
        if (_L - _M <= _M - _F)
            _Sort(_M, _L, (Integer*)0), _L = _M;
        else
            _Sort(_F, _M, (Integer*)0), _F = _M; }}
template<class _RI, class _Ty> inline
    void _Sort_0(_RI _F, _RI _L, _Ty *)
    {if (_L - _F <= std::_SORT_MAX)
        _Insertion_sort(_F, _L);
    else
        {_Sort(_F, _L, (_Ty *)0);
        _Insertion_sort(_F, _F + std::_SORT_MAX);
        for (_F += std::_SORT_MAX; _F != _L; ++_F)
            _Unguarded_insert(_F, _Ty(*_F)); }}
template<class _RI> inline
    void quicksort(_RI _F, _RI _L)
    {_Sort_0(_F, _L, (Integer*)0); }
template<class _RI, class _Ty> inline
    _RI _Unguarded_partition(_RI _F, _RI _L, _Ty _Piv)
    {for (; ; ++_F)
        {for (; *_F < _Piv; ++_F)
            ;
        for (; _Piv < *--_L; )
            ;
        if (_L <= _F)
            return (_F);
        std::iter_swap(_F, _L); }}
template<class _RI> inline
    void _Insertion_sort(_RI _F, _RI _L)
    {_Insertion_sort_1(_F, _L, (Integer*)0); }
template<class _BI, class _Ty> inline
    void _Insertion_sort_1(_BI _F, _BI _L, _Ty *)
    {if (_F != _L)
        for (_BI _M = _F; ++_M != _L; )
            {_Ty _V = *_M;
            if (!(_V < *_F))
                _Unguarded_insert(_M, _V);
            else
                {std::copy_backward(_F, _M, _M + 1);
                *_F = _V; }}}
template<class _BI, class _Ty> inline
    void _Unguarded_insert(_BI _L, _Ty _V)
    {for (_BI _M = _L; _V < *--_M; _L = _M)
        *_L = *_M;
    *_L = _V; }
}

namespace fixed {
template<class _Ty> inline
    _Ty& _Median(_Ty& _X, _Ty& _Y, _Ty& _Z)
        {
            if (_X < _Y) {
                if(_Z < _Y) {
                    if(_X < _Z) {
                        std::swap(_Y,_Z);
                    } else {
                        _Ty temp( _Z );
                        _Z = _Y;
                        _Y = _X;
                        _X = temp;
                    }
                }
            } else {
                if(_Z < _Y) {
                    std::swap(_X,_Z);
                } else {
                    if(_X < _Z) {
                        std::swap(_X,_Y);
                    } else {
                        _Ty temp( _X );
                        _X = _Y;
                        _Y = _Z;
                        _Z = temp;
                    }
                }
            }
            return _Y;
        }

template<class _RI, class _Ty> inline
void _Sort(_RI _F, _RI _L, _Ty *)
{
    for (; std::_SORT_MAX < _L - _F; )
    {
        _Ty& pivot = _Median(*_F, *(_F + (_L - _F) / 2), *(_L - 1) );
        _RI _M = _Unguarded_partition( _F+1, _L-1, pivot );
        if (_L - _M <= _M - _F)
            _Sort(_M, _L, (Integer*)0), _L = _M;
        else
            _Sort(_F, _M, (Integer*)0), _F = _M;
    }
}
template<class _RI, class _Ty> inline
    void _Sort_0(_RI _F, _RI _L, _Ty *)
    {if (_L - _F <= std::_SORT_MAX)
        _Insertion_sort(_F, _L);
    else
        {_Sort(_F, _L, (_Ty *)0);
        _Insertion_sort(_F, _F + std::_SORT_MAX);
        for (_F += std::_SORT_MAX; _F != _L; ++_F)
            _Unguarded_insert(_F, _Ty(*_F)); }}
template<class _RI> inline
    void quicksort(_RI _F, _RI _L)
    {_Sort_0(_F, _L, (Integer*)0); }
template<class _RI, class _Ty> inline
    _RI _Unguarded_partition(_RI _F, _RI _L, _Ty _Piv)
    {for (; ; ++_F)
        {for (; *_F < _Piv; ++_F)
            ;
        for (; _Piv < *--_L; )
            ;
        if (_L <= _F)
            return (_F);
        std::iter_swap(_F, _L); }}
template<class _RI> inline
    void _Insertion_sort(_RI _F, _RI _L)
    {_Insertion_sort_1(_F, _L, (Integer*)0); }
template<class _BI, class _Ty> inline
    void _Insertion_sort_1(_BI _F, _BI _L, _Ty *)
    {if (_F != _L)
        for (_BI _M = _F; ++_M != _L; )
            {_Ty _V = *_M;
            if (!(_V < *_F))
                _Unguarded_insert(_M, _V);
            else
                {std::copy_backward(_F, _M, _M + 1);
                *_F = _V; }}}
template<class _BI, class _Ty> inline
    void _Unguarded_insert(_BI _L, _Ty _V)
    {for (_BI _M = _L; _V < *--_M; _L = _M)
        *_L = *_M;
    *_L = _V; }
}


template<class I>
void is_sorted( I first, I last )
{
    if( first != last ) {
        I next = first;
        ++next;
        while( next != last ) {
            if( *next < *first ) {
                std::cout << "not sorted!" << std::endl;
                return;
            }
            first = next;
            ++next;
        }
        std::cout << "sorted!" << std::endl;
    }
}

int main()
{
    int i;
    std::vector<Integer> vec;

    std::cout << std::endl << std::endl;
    std::cout << "ordering vector in a special way..." << std::endl;
    for( i=1; i<=10000; ++i ) { vec.push_back(i); }
    vec.push_back(0);
    std::cout << "calling broken::quicksort on the vector..." << std::endl;
    Integer::ClearStats();
    broken::quicksort( vec.begin(), vec.end() );
    Integer::ReportStats();
    is_sorted( vec.begin(), vec.end() );
    std::cout << std::endl << "randomly shuffling vector..." << std::endl;
    std::random_shuffle( vec.begin(), vec.end() );
    std::cout << "calling broken::quicksort on the vector..." << std::endl;
    Integer::ClearStats();
    broken::quicksort( vec.begin(), vec.end() );
    Integer::ReportStats();
    is_sorted( vec.begin(), vec.end() );

    vec.clear();

    std::cout << std::endl << std::endl;
    std::cout << "ordering vector in a special way..." << std::endl;
    for( i=1; i<=10000; ++i ) { vec.push_back(i); }
    vec.push_back(0);
    std::cout << "calling fixed::quicksort on the vector..." << std::endl;
    Integer::ClearStats();
    fixed::quicksort( vec.begin(), vec.end() );
    Integer::ReportStats();
    is_sorted( vec.begin(), vec.end() );
    std::cout << std::endl << "randomly shuffling vector..." << std::endl;
    std::random_shuffle( vec.begin(), vec.end() );
    std::cout << "calling fixed::quicksort on the vector..." << std::endl;
    Integer::ClearStats();
    fixed::quicksort( vec.begin(), vec.end() );
    Integer::ReportStats();
    is_sorted( vec.begin(), vec.end() );

    return 0;
}



-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

gtalvola@parlance-ncs.com wrote in article <6n8ngq$o2d$1@nnrp1.dejanews.com>...
> After looking at the code for std::sort in VC++ 5.0, here's how I think it is
> flawed.  The algorithms book I have in front of me (Data Structures & Their
> Algorithms by Lewis and Denenberg) describes a version of median-of-three
> quicksort which is subtly different from what is implemented by VC++ 5.0 and
> by XTL.  In the version described in Lewis and Denenberg, when you take the
> median of the first, middle, and last elements to determine the pivot, you
> _sort_ those three elements in-place and then use the middle element as the
> pivot. The algorithms in VC++ 5.0 and in XTL do not sort the three elements,
> but instead just use the median of the three as the pivot without rearranging
> them. I believe that the version of the algorithm in Lewis and Denenberg does
> not suffer from quadratic performance on this input sequence because of the
> sorting of the first, middle, and last elements.

Uh, I don't see how is the *median* of three elements different if you sort the
elements and take the middle one or if you evaluate the template function:

  // TEMPLATE FUNCTION _Median
template<class _Ty> inline
 _Ty _Median(_Ty _X, _Ty _Y, _Ty _Z)
  {if (_X < _Y)
   return (_Y < _Z ? _Y : _X < _Z ? _Z : _X);
  else
   return (_X < _Z ? _X : _Y < _Z ? _Z : _Y); }

The above is taken from <algorithm> as shipped with VC++ V5.0. Am I missing
something?

> And the moral of the story for anyone whose std::sort uses this flawed
> median-of-three quicksort algorithm is to consider switching to using
> std::partial_sort instead, because the version of median-of-three being used
> is too vulnerable to quadratic behavior.  If it happened to me, it can happen
> to you :-)
>
> I think the numbers that have been posted in this thread show that the SGI
> introsort implementation also suffers from initial quadratic behavior, before
> it switches to heapsort.  So it too would benefit from using the correct
> median-of-three algorithm, in that it would be much less likely to have to
> switch to heapsort.  Of course this is much less of a "problem" with introsort
> than it is with plain quicksort.

If the median calculation is indeed not flawed, as I believe, then I think it
renders some of your qualitative judgements about implementations and
algorithms a bit suspect.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

gtalvola@parlance-ncs.com wrote:
>
> In article <359862D7.2067328A@acm.org>,
>   Pete Becker <petebecker@acm.org> wrote:
>
> >       Incidentally, offhand I don't think that "sort[ing] the three elements
> > in place" affects this at all. You still get the same bad pivot element,
> > and you still get the same highly unequal partitions. You sort the three
> > elements in order to be able to choose the median.
>
> It actually does solve the problem, because sorting those 3 elements prevents
> the bad pivot from being selected on the next pass.  Here's sample code to
> prove it, containing first the quicksort implementation as implemented in VC++
> 5.0, and then my fixed version which sorts the 3 elements as it picks the
> median.

 "Doctor, it hurts when I do this." "So don't do that."
 Making the behavior change is not the same as solving the problem.
Reread the part of my message that you snipped. When you push a problem
away from one sort of input sequence you push it onto another. The fact
that it's out of your way in your particular example does not mean there
was anything wrong with the initial implementation, or that the version
that works better with your input is better in the general case. In
fact, I'll bet that the user whose data sorts in N^2 with your version
but logN with the initial one will be very unhappy with your version.

> For example, according to David Musser's
> article "Introspective Sorting and Selection Algorithms", sequences like
>
> 1 11 3 13 5 15 7 17 9 19 2 4 6 8 10 12 14 16 18 20
>
> will cause quadratic behavior even with the fixed median-of-three.  Still,
> this is signficantly less likely to arise in practice than the sequence I ran
> into:
>
> 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1
>

Why is it "significantly less likely"? If you're randomly choosing
numbers from 1 to 20 those two sequences will occur with exactly the
same probability. If you're relying on special knowledge of a particular
problem domain, you may be right. But we're talking about general
purpose algorithms here, not algorithms tuned for a particular type of
input data.
 Further, it's important to be able to explain to people what they need
to watch out for when they use a sorting algorithm. If the second
example is a typical problem case, it's easy: "don't use quicksort with
nearly ordered data." How would you describe the first sequence, in
order to avoid setting a trap for users?

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

gtalvola@parlance-ncs.com wrote:
>> After looking at the code for std::sort in VC++ 5.0, here's how I
>> think it is flawed.  The algorithms book I have in front of me (Data
>> Structures & Their Algorithms by Lewis and Denenberg) describes a
>> version of median-of-three quicksort which is subtly different from
>> what is implemented by VC++ 5.0 and by XTL.  ...

P.J. Plauger wrote:
> Uh, I don't see how is the *median* of three elements different if you
> sort the elements and take the middle one or if you evaluate the
> template function:
>  ...
> Am I missing something?

If I understand gtalvola's theory correctly, I think he means that
the sort function works better if the median selection sorts the
values in place, i.e., swaps the elements of the container so that
they end up in sorted order.  Rearranging the container elements,
as opposed to simply selecting one and leavng them where they are,
apparently has beneficial effects on the rest of the sorting
process.

-- David R. Tribble, dtribble@technologist.com --
-- C++, the PL/1 of the 90s.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <01bda0af$f3675b80$8a1ec2d0@porky>,
  "P.J. Plauger" <pjp@dinkumware.com> wrote:
>
> Why do you suspect that it may not be entirely correct if DeltaLogic's XTL
> exhibits the same behavior? However hard you worked at it, you found exactly
> the most perverse initial order for a median-of-three quicksort. It is indeed
> quadratic.

I didn't have to work hard to find the sequence -- it arose naturally in the
course of my work.  And from all that I've read about it, median-of-three
quicksort is supposed to be very robust to a wide variety of input sequences,
so I was very surprised to see quadratic behavior.

After looking at the code for std::sort in VC++ 5.0, here's how I think it is
flawed.  The algorithms book I have in front of me (Data Structures & Their
Algorithms by Lewis and Denenberg) describes a version of median-of-three
quicksort which is subtly different from what is implemented by VC++ 5.0 and
by XTL.  In the version described in Lewis and Denenberg, when you take the
median of the first, middle, and last elements to determine the pivot, you
_sort_ those three elements in-place and then use the middle element as the
pivot. The algorithms in VC++ 5.0 and in XTL do not sort the three elements,
but instead just use the median of the three as the pivot without rearranging
them. I believe that the version of the algorithm in Lewis and Denenberg does
not suffer from quadratic performance on this input sequence because of the
sorting of the first, middle, and last elements.

> > I've switched to using partial_sort to avoid this pitfall.  (Also, I'm
> > surprised that on a randomly ordered vector, quicksort was not clearly
> > superior to heapsort -- quicksort actually required _more_ comparisons but
> > fewer assignments.  In some applications, partial_sort would be faster.)
>
> I suspect you're overreacting, and possibly overanalyzing. In any event, STL
> gives you oodles of algorithms to choose from, so take your pick. To me, the
> moral of the story is that introsort is well worth the small amount of
bookkeeping
> it adds to quicksort. Of course, it also drags in the heap stuff, so its
code-space
> efficiency isn't as impressive as its speed or time complexity, but what the
heck.

And the moral of the story for anyone whose std::sort uses this flawed
median-of-three quicksort algorithm is to consider switching to using
std::partial_sort instead, because the version of median-of-three being used
is too vulnerable to quadratic behavior.  If it happened to me, it can happen
to you :-)

I think the numbers that have been posted in this thread show that the SGI
introsort implementation also suffers from initial quadratic behavior, before
it switches to heapsort.  So it too would benefit from using the correct
median-of-three algorithm, in that it would be much less likely to have to
switch to heapsort.  Of course this is much less of a "problem" with introsort
than it is with plain quicksort.


- Geoff Talvola
  gtalvola@parlance-ncs.com

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Oleg Zabluda <zabluda@math.psu.edu> wrote in article <6mv5eu$hde@marianna.psu.edu>...
> gtalvola@parlance-ncs.com wrote:
> Here is what I get with egcs, SGI STL and -D_SVID_SOURCE for
> lrand48:
> .....
> ordering vector in a special way...
> calling std::sort on the vector...
> number of comparisons: 407553
> number of assignments: 157751

Well, it makes me feel a little better to know that my implementation of
introsort compares favorably with the SGI version:

> ordering vector in a special way...
> calling std::sort on the vector...
> number of comparisons: 287902
> number of assignments: 157923

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

gtalvola@parlance-ncs.com wrote in article <6mtlsp$3kb$1@nnrp1.dejanews.com>...
> Matt Austern wrote:
> >                                                                                               I'm
> > not aware of any library vendors that provide a sort() with worst-case
> > behavior for already-sorted sequences.  Every implementation I'm aware
> > of uses median-of-three quicksort, which has worst case behavior for
> > rather complicated and rare input sequences.
>
> I would have agreed with you a week ago, but just last week I ran into an
> input sequence in practice which caused Visual C++ 5.0's version of std::sort
> to blow up to quadratic behavior.  This was not some complicated and rare
> input sequence -- it was just a large already-sorted array with an additional
> element less than all other elements tacked onto the end.  This causes VC++'s
> version of std::sort to blow up to O(N^2).
>
> VC++ uses a version of median-of-three quicksort, although I suspect that it
> may not be an entirely correct implementation, because all of the literature
> suggests that it is difficult to break median-of-three quicksort, but I was
> able to break theirs so easily.

Why do you suspect that it may not be entirely correct if DeltaLogic's XTL
exhibits the same behavior? However hard you worked at it, you found exactly
the most perverse initial order for a median-of-three quicksort. It is indeed
quadratic.

> Here's a program which demonstrates the problem.  std::sort fails miserably
> on the almost-sorted sequence.

Well, it gets the right answer, and it meets the complexity specifications of
the C++ Standard. One man's miserable failure is another man's conforming
behavior.

>                                                   I'd be curious to know if other
> implementations of STL also suffer from the same problem.  I know that
> DeltaLogic's XTL does have the same problem, while SGI's STL does not because
> it uses introsort.

I too use introsort these days -- hats off to Dave Musser. Our latest version of
template function sort, given the perverse input sequence, shows the following
changes.

> // ordering vector in a special way...
> // calling std::sort on the vector...
> // number of comparisons: 50074820  BECOMES  287902
> // number of assignments: 29985       BECOMES  157923

I suspect that in most cases the extra assignments from make_heap/sort_heap
are more than repaid by the enormous savings in comparisons. Unless maybe
you're sorting screen images with integer keys...

> I've switched to using partial_sort to avoid this pitfall.  (Also, I'm
> surprised that on a randomly ordered vector, quicksort was not clearly
> superior to heapsort -- quicksort actually required _more_ comparisons but
> fewer assignments.  In some applications, partial_sort would be faster.)

I suspect you're overreacting, and possibly overanalyzing. In any event, STL
gives you oodles of algorithms to choose from, so take your pick. To me, the
moral of the story is that introsort is well worth the small amount of bookkeeping
it adds to quicksort. Of course, it also drags in the heap stuff, so its code-space
efficiency isn't as impressive as its speed or time complexity, but what the heck.

Thanks for supplying some interesting numbers.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

gtalvola@parlance-ncs.com wrote:

[...]

: ////////////////////////////////////////////////////////////////
: // this program when compiled on VC++ 5.0, Service Pack 3
: // produces the following output:
: //
: // ordering vector in a special way...
: // calling std::partial_sort on the vector...
: // number of comparisons: 138105
: // number of assignments: 148122
: //
: // randomly shuffling vector...
: // calling std::partial_sort on the vector...
: // number of comparisons: 136839
: // number of assignments: 148014
: //
: //
: // ordering vector in a special way...
: // calling std::sort on the vector...
: // number of comparisons: 50074820
: // number of assignments: 29985
: //
: // randomly shuffling vector...
: // calling std::sort on the vector...
: // number of comparisons: 161079
: // number of assignments: 81879
: //
: ////////////////////////////////////////////////////////////////

[...]

Wow! 50 Megaassignements!

Here is what I get with egcs, SGI STL and -D_SVID_SOURCE for
lrand48:

ordering vector in a special way...
calling std::partial_sort on the vector...
number of comparisons: 138105
number of assignments: 148122

randomly shuffling vector...
calling std::partial_sort on the vector...
number of comparisons: 136640
number of assignments: 147749


ordering vector in a special way...
calling std::sort on the vector...
number of comparisons: 407553
number of assignments: 157751

randomly shuffling vector...
calling std::sort on the vector...
number of comparisons: 158859
number of assignments: 82958

Oleg.
--
Life is a sexually transmitted, 100% lethal disease.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern wrote:

> The standard allows sort() to be implemented in such a way that its
> complexity is worst-case quadratic.  However, (1) Some implementations
> have versions of sort that have guaranteed O(N log(N)) worst-case
> complexity (SGI has had such an implementation for more than a year;
> it uses introsort instead of quicksort), and I expect that all library
> vendors will have improved versions of sort() before long; and (2) I'm
> not aware of any library vendors that provide a sort() with worst-case
> behavior for already-sorted sequences.  Every implementation I'm aware
> of uses median-of-three quicksort, which has worst case behavior for
> rather complicated and rare input sequences.

I would have agreed with you a week ago, but just last week I ran into an
input sequence in practice which caused Visual C++ 5.0's version of std::sort
to blow up to quadratic behavior.  This was not some complicated and rare
input sequence -- it was just a large already-sorted array with an additional
element less than all other elements tacked onto the end.  This causes VC++'s
version of std::sort to blow up to O(N^2).

VC++ uses a version of median-of-three quicksort, although I suspect that it
may not be an entirely correct implementation, because all of the literature
suggests that it is difficult to break median-of-three quicksort, but I was
able to break theirs so easily.

Here's a program which demonstrates the problem.  std::sort fails miserably
on the almost-sorted sequence. I'd be curious to know if other
implementations of STL also suffer from the same problem.  I know that
DeltaLogic's XTL does have the same problem, while SGI's STL does not because
it uses introsort.

I've switched to using partial_sort to avoid this pitfall.  (Also, I'm
surprised that on a randomly ordered vector, quicksort was not clearly
superior to heapsort -- quicksort actually required _more_ comparisons but
fewer assignments.  In some applications, partial_sort would be faster.)


////////////////////////////////////////////////////////////////
// this program when compiled on VC++ 5.0, Service Pack 3
// produces the following output:
//
// ordering vector in a special way...
// calling std::partial_sort on the vector...
// number of comparisons: 138105
// number of assignments: 148122
//
// randomly shuffling vector...
// calling std::partial_sort on the vector...
// number of comparisons: 136839
// number of assignments: 148014
//
//
// ordering vector in a special way...
// calling std::sort on the vector...
// number of comparisons: 50074820
// number of assignments: 29985
//
// randomly shuffling vector...
// calling std::sort on the vector...
// number of comparisons: 161079
// number of assignments: 81879
//
////////////////////////////////////////////////////////////////

#include <algorithm>
#include <iostream>
#include <vector>

struct Integer {
    Integer(): value(0) {}
    Integer( int i ): value(i) {}

    bool operator<( const Integer& I ) const
    {
        ++num_comparisons;
        return value<I.value;
    }

    void operator=( const Integer& I )
    {
        ++num_assignments;
        value = I.value;
    }

    int value;


    static void ReportStats()
    {
        std::cout << "number of comparisons: "
                  << num_comparisons << std::endl;
        std::cout << "number of assignments: "
                  << num_assignments << std::endl;
        ClearStats();
    }
    static void ClearStats()
    {
        num_comparisons = 0;
        num_assignments = 0;
    }
    static int num_comparisons;
    static int num_assignments;
};

int Integer::num_comparisons = 0;
int Integer::num_assignments = 0;


int main()
{
    int i;
    std::vector<Integer> vec;

    std::cout << "ordering vector in a special way..." << std::endl;
    for( i=1; i<=10000; ++i ) { vec.push_back(i); }
    vec.push_back(0);
    std::cout << "calling std::partial_sort on the vector..." << std::endl;
    Integer::ClearStats();
    std::partial_sort( vec.begin(), vec.end(), vec.end() );
    Integer::ReportStats();
    std::cout << std::endl << "randomly shuffling vector..." << std::endl;
    std::random_shuffle( vec.begin(), vec.end() );
    std::cout << "calling std::partial_sort on the vector..." << std::endl;
    Integer::ClearStats();
    std::partial_sort( vec.begin(), vec.end(), vec.end() );
    Integer::ReportStats();

    vec.clear();

    std::cout << std::endl << std::endl;
    std::cout << "ordering vector in a special way..." << std::endl;
    for( i=1; i<=10000; ++i ) { vec.push_back(i); }
    vec.push_back(0);
    std::cout << "calling std::sort on the vector..." << std::endl;
    Integer::ClearStats();
    std::sort( vec.begin(), vec.end() );
    Integer::ReportStats();
    std::cout << std::endl << "randomly shuffling vector..." << std::endl;
    std::random_shuffle( vec.begin(), vec.end() );
    std::cout << "calling std::sort on the vector..." << std::endl;
    Integer::ClearStats();
    std::sort( vec.begin(), vec.end() );
    Integer::ReportStats();

    return 0;
}


--


- Geoff Talvola
  Parlance Corporation
  gtalvola@parlance-ncs.com



-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]