Author: Stan Eisenstat
Subject: Re: CPSC223 xQuick.pl
Date: Wednesday, 01 Apr 2020, 18:32:23

    > I saw your recent message about testing whether our code is actually
    > running quicksort. I pass all 15 test cases and the number of adds/pushes
    > I use is always <= 2#compares + n. However, for some inputs, when I run
    > xQuick.pl, it says I am not using quicksort. I have attached my code to
    > this email so that maybe you can give me more insight into why it is
    > saying what it does on xQuick.pl.

The problem is the sequence

  if (strncmp(...) > 0)
     ...
  else if (strncmp(...) <= 0)
     ...

which performs the comparison twice.  This inflates the
number of compares and thus the limit C*#compares + N on
the number of calls to pushdD() and addD(), making it
easier to satisfy.

--Stan-