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.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no 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: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,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.96Aug12201351@spectre.mitre.org>#1/1
X-Deja-AN: 173804676
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 <839708378snz@genesis.demon.co.uk> Lawrence Kirby <fred@genesis.demon.co.uk> writes:

   I said:

   >Quicksort step of picking up the cards is O(n), not O(n log n)
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

  > What does this phrase mean? Quicksort is an (n log n) (average time)
  > operation. Building a heap is an O(n) operation.

  It means that when you finish the first stage of the Quicksort, you
have several piles laid out on the table.  Completing the sort
requires picking them up in order.  For heap sort, building the heap
is also an O(n log n) operation, since you maintain a heap.  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.

   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.  (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.)
--

					Robert I. Eachus

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