Re: comparison of sorting algorithms

From: CBFalconer (cbfalconer_at_yahoo.com)
Date: 06/14/04 

Date: Mon, 14 Jun 2004 12:50:24 GMT

Peter Ammon wrote:
>
> CBFalconer wrote:
>
> > Dan Tex1 wrote:
> >
> > ... snip ...
> >
> >>I tested a hybrid, non-recursive quicksort that uses insertion
> >>sort as partitions of data to be sorted become smaller. I tried
> >>it with different types of data in all sorts of different
> >>starting orders. I tried small data sets and large ones ( many
> >>megabytes of data, files 30, 40 MB and larger ). I found that
> >>it worked great for pretty much eveything.
> >
> >
> > There is always an input that will make it run in O(N*N). See:
> >
> > SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999)
> > A Killer Adversary for Quicksort
> > M. D. MCILROY
> >
>
> But see introsort, a variant of Quicksort that does not.
>
> http://www.nist.gov/dads/HTML/introspectiveSort.html
> http://citeseer.ist.psu.edu/582691.html

The following from the first link above:

   Definition: A variant of quicksort which switches to
   heapsort for pathological inputs, that is, when execution
   time is becoming quadratic.

   Also known as introsort.

Found at <http://www.cs.rpi.edu/~musser/gp/introsort.ps>

I have not read the paper yet, but it seems to me that one might
as well code for heapsort in the first place. I would expect the
result to be no more than 25% slower than a quicksort, and to
always have NlnN performance. 

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

Relevant Pages

  • Re: Introsort
    ... >>Can someone tell me why Musser's Introsort algorithm switches ... >>to Heapsort when the recursion depth of Quicksort gets too ... >>does Quicksort, so we don't seem to be gaining anything. ... When the introspective part of introsort starts running, ...
    (comp.programming)
  • Re: Fastcode poll - Should Sort include worst case situations
    ... It will switch to heapsort if quicksort goes bad. ... And I would use the hybrid introsort for Fast project, ... With old versions of quicksort, you always recursively sort the smaller ...
    (borland.public.delphi.language.basm)
  • Re: Help needed for a sorting code in the literature
    ... but this has impact on a recent sorting algorithm called ... Introsort authors claimed that Quicksort was generally always better, ... and that Heapsort should only be switched to when it seems that you ... Look the issue is branch prediction. ...
    (sci.crypt)
  • Re: Heapsort and quicksort
    ... Quicksort and HeapSort actually differ in behaviour. ... algorithm but also for an efficient way of implementing a priority queue. ...
    (comp.lang.java)
  • Re: Quicksort
    ... Falling back to a heapsort is basically what introsort does. ... quicksort, so just do that, and you immediately have a worst case ... anyways, even though cocktail sort is, theoretically O, here is an odd ... void BGBGC_ShiftLObj_Swap(int i, int j) ...
    (comp.programming)