Re: Teaching sorts [was Re: What's the best language to start with?]

[Lawrence Kirby <fred@genesis.demon.co.uk>]

In article <EACHUS.96Aug12201351@spectre.mitre.org>
           eachus@spectre.mitre.org "Robert I. Eachus" writes:

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

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.

  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".

> 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".

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

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

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

-- 
-----------------------------------------
Lawrence Kirby | fred@genesis.demon.co.uk
Wilts, England | 70734.126@compuserve.com
-----------------------------------------