From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
From: eachus@spectre.mitre.org (Robert I. Eachus)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/13
Message-ID: <EACHUS.96Aug13143444@spectre.mitre.org>
X-Deja-AN: 173956723
references: <31FBC584.4188@ivic.qc.ca>
 <01bb83f5$923391e0$87ee6fce@timpent.airshields.com>
organization: The Mitre Corp., Bedford, MA.
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-13T00:00:00+00:00
List-Id: <comp.lang.ada>


In article <839939925snz@genesis.demon.co.uk> Lawrence Kirby <fred@genesis.demon.co.uk> writes:

  > Then you have to sort each pile recursively bringing you back to
  > O(n log n).  Picking up a pile of cards isn't what determines the
  > running time of quicksort.

   Sorry if it was confusing, in the quicksort approach you lay down
the top card, then sort the remainder of the (current) deck to the
left and right.  Pick up the piles to the left and right (separately)
and do the same.  Iterate until you pick up a small enough pile to
sort in place.  (Your choice of one, two or three cards.)

   That completes the first part of the sort.  Now pick up the cards
left to right.  That is the second step and obviously O(n).

  (I said:)

  > > For heap sort, building the heap
  > > is also an O(n log n) operation, since you maintain a heap.

  > Wrong, you don't maintain a heap, you just build it. If you approach
  > that correctly it is an O(n) operation. Quoting from Sedgewick:

  > "... its can in fact be proven that the construction process takes
  >  linear time since so many small heaps are processed".

  If you use the canonical heapsort it is O(2n) average, O(n log n)
worst case.  (The worst case is when each card added to the bottom of
the heap propagates to the top, using the usual version of the sort,
or propagates to bottom in the other definition, where you start with
an unsorted list/heap and sort in place.)

  (I said:) 

  > > However
  > >picking up the cards is also N log N since you have to maintain the
  > >heap property, and in any case you pick them up one at a time.

  > However there is a lot more to quicksort than just "picking up the cards".

  Of course there is. But here I was saying that when you get to the
stage of picking up cards, heapsort is slower.  And I also pointed
out that quicksort is usually slower up to that point:

  >>   Try the experiment.  A good heapsorter will finish heapifying
  >> and pick up the first card first.  A couple seconds later, the
  >> quicksorter will finish the job, assuming the cards were well
  >> shuffled.

  > I did. It took slightly over twice as long to quicksort a pack of
  >52 playing cards than it did to create a heap from them. The only
  >real thing of note is that you can perform the individual
  >operations required for partitioning much quicker than the careful
  >card repositioning you need to perform to construct a heap. That
  >does reflect to some extent the respective computer implementations
  >but the effect is much more pronounced with cards. Overall building
  >a heap required far fewer operations than the quicksort.

   We are in violent agreement here.  I said the heapsorter would
finish building the heap before the quicksorter picked up a card.  But
I also said that the next stage for quicksorting is much faster than
converting a heap into a sorted stack.

   >>    (Of course, one of the fun steps is to tell the students to
   >> repeat the exercise--without shuffling.  Now the race is
   >> between quicksort and bubblesort for last place.)

   > With cards it is easy to implement a random or an approximate
   > half way pivot selection. Which prings up the question of
   > precisely what algorithms are actually being used.

   Yes it is, but that is not part of quicksort as invented, and on
average slows quicksort down.  If you are concerned about poor worst
case performance you use a heap or radix sort.  You know that, I know
that.  After this demonstration, the students know that. ;-)

  > Further discussion of this ought to go to a newsgroup such as
  > comp.programming or via email.

  In hasn't been in comp.programming or I would have set followups
accordingly.  But I think we have worn the subject out.  It is a cute
computer lab session, it teaches some important fundamentals, and
those lessons are important.  Dexterity effects and the like are
distractions.  But it actually is nice that the time for quicksort
varies as much as it does.  It not only adds interest to the lab,
but it means that the students aren't embarrassed by the results of
any particular trial.


--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...