Re: hc11 program help

From: Max (mtj2_at_btopenworld.com)
Date: 03/02/04 

Date: Tue, 2 Mar 2004 17:04:04 +0000 (UTC)

On Sun, 29 Feb 2004 18:52:08 GMT, CBFalconer wrote:

>Heapsort and mergesort can easily function in place.

I think we must be talking about different algorithms here. NIST don't
categorize heapsort as an in-place algorithm:
http://www.nist.gov/dads/HTML/heapSort.html
http://www.nist.gov/dads/HTML/inplacesort.html

I've never seen an in-place merge sort either, though there's
apparently mention of them in the literature:
http://www.nist.gov/dads/HTML/mergesort.html

I suggest that any implementation claiming to be an in-place heap or
merge sort is likely to actually be a partition-exchange algorithm in
disguise, and therefore a version of Hoare's quicksort. It would be
interesting to be proved wrong, though!

>Unlike
>quicksort, their worst case performance remains O(NlogN). For any
>'median' or other partitioning quicksort can be driven into worst
>case (N*N) performance. See:

That's true, of course. I only claimed Mo3 was a fix for quadratic
behaviour with ordered input, which is not uncommon in real-world
cases. I have never seen any evidence of an Mo3 quicksort going
quadratic, but there is always a vanishingly small chance of it.

>SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999)

Thanks for that. I'd heard of this paper, but never seen a citation to
track it down. A very interesting read.

Do you perchance have a link to the paper co-authored by McIlroy and
cited as Ref 3? I'm curious as to the claim of real-world quadratic
behaviour.

>In addition, C library qsort need not be quicksort.

>From a strictly legalistic view, that's true, since there's nothing in
the official C standards that mandates it's use. But I do strongly
believe there's a traditional obligation to use it, since it's what
any programmer writing "portable" C is entitled to expect.

I don't personally know of a qsort that isn't a variation or hybrid of
a partitiion-exchange (and I wouldn't use it if I did). The original
Ritchie/Thompson/Plauger libraries all used quicksort.

I'd also draw your attention to the paper you yourself cited. In the
very first paragraph:
"a specific adversary for the standard C qsort function"

Basically, if it ain't quicksort, don't call it qsort. To do so is
misleading, and not really in the C "spirit". 

-- 
  Max

Relevant Pages

  • Re: hc11 program help
    ... >needs only Oextra storage, so it's actually even better than the ... >quicksort" in whatever disguise. ... >any particular algorithm being the implementation of qsort. ... and provide a quicksort implementation for qsort. ...
    (comp.arch.embedded)
  • Re: Help needed for a sorting code in the literature
    ... Quicksort with perfect pivot selection is guaranteed ... > pivot selection algorithm is inefficient. ... branch prediction problem. ...
    (sci.crypt)
  • Re: smuggling data in and out of alarm handlers and the like
    ... it triggered an unstable sort in... ... Software exploratorium: The trouble with qsort. ... about the Quicksort algorithm; the first does acknowledge that qsort ... sort algorithm under the covers in the final analysis. ...
    (comp.lang.c)
  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: What is the most fast sorting algorithm?
    ... Worst case for quicksort using naive partition algorithms ... Using ramdomized partition algorithm, ... I don't think any of these algorithms detect quadratic behavior. ... Introsort cuts off to heapsort when the stack ...
    (comp.programming)