Author: Stan Eisenstat
Subject: Re: [Cs223] #compares
Date: Monday, 30 Mar 2020, 20:02:39

    > Message Posted By: Unknown
    >
    > I've been messing around with Hwk4/Stats.pl for a while, and it seems that
    > #compares is calculated by counting the number of calls Qsort makes to
    > strncmp. ...

Stats.pl reports the number of calls to strcmp() or
strncmp() where both strings are located in the heap.
=====

    >      ... So are we also limited on how many times our Qsort calls strncmp
    > as well? Or will that be tested by seeing if our Qsort is actually
    > quicksort, i.e. follows a Qsort pattern? Otherwise, if we just throw in a
    > bunch of random strncmps, wouldn't #compares just go up with it?

As you note, Qsort can pass Tests #303 and #304 by doing
extra compares.  Thus I developed Hwk4/Tests/xQuick.pl
to verify that Qsort implements quickSort WITHOUT doing
extra compares.
=====

    > I guess what I'm asking is, how is #compares calculated in Stats.pl? When
    > I run /c/cs223/Hwk4/Tests/Stats.pl /c/cs223/Hwk4/Tests/f007
    > /c/cs223/Hwk4/Tests/f057 I get 410 compares instead of 351, which is what
    > appeared here when Professor Eisenstat used it.

The #compares depends on the choice of splitters, which
in turn depends on how you implement quickSort using two
stacks and a queue (or some other collection of Deques).

Running the same test using Hwk4/Qsort with Tests/f007
and a permuted (by the shuf command) copy of Tests/t057
produced numbers as low as 310 and as high at 447.  Thus
410 is well within bounds.

--Stan-