Re: Sort.array easily degenerates

From: doligez@pa.dec.com
Date: Wed Mar 10 1999 - 00:03:05 MET


From: doligez@pa.dec.com
Message-Id: <199903092303.AA14481@six.pa.dec.com>
To: OCAML <caml-list@inria.fr>
Subject: Re: Sort.array easily degenerates
In-Reply-To: Message of Tue, 9 Mar 1999 11:44:42 +0100
    from Xavier Leroy <Xavier.Leroy@inria.fr>
Date: Tue, 09 Mar 1999 15:03:05 -0800

>From: Xavier Leroy <Xavier.Leroy@inria.fr>

>The Sort.array implementation is Quicksort with insertion sort for
>small partitions, as suggested in Sedgewick. I should know better
>than take some code out of an algorithms textbook and expect that it
>will work well...

There's no way to implement Sedgewick's quicksort with the interface
given in sort.mli. You'd need two comparison functions, one for ">="
and one for "<=". That explains the degenerate case when all the
elements are equal.

And it degenerates on already-sorted data because you swap the pivot
with the right-most element. As a consequence, one of the subarrays
has its two highest elements in first and last positions, which makes
the median-of-three degenerate. I think this bug is also in
Sedgewick's pseudo-code.

Also, you should recurse on the smallest subarray first, not the
largest.

I vote for Shellsort.

-- Damien



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:20 MET