Author: Stan Eisenstat
Subject: Re: [Cs223] deduction for #compares
Date: Wednesday, 01 Apr 2020, 15:04:19

    > Message Posted By: Unknown
    >
    > In the specification, it is stated that requiring more than 2*compares+N
    > calls will incur a 2-point deduction, while more than 4*compares+N will
    > incur an 8-point deduction.
    >
    > If we pass the 2 public tests that check for the number of compares, are
    > we safe from this deduction? Will there be private tests that check the
    > number of compares based on another input?

Yes, if you have implemented quickSort, since Tests #403
and #404 impose these deductions.

I added the caveat because implementations of other
sorting algorithms and implementations of quickSort that
do extra comparisons may be able to pass these tests,
but are not valid.

As I posted earlier:

  Date: 30 Mar 2020 17:29:18 -0400 (Mon)
  Subject: Does your Qsort implement quickSort
   
  I wrote a tool Hwk4/Tests/xQuick.pl that examines the
  sequence of comparisons that Qsort makes and attempts to
  determine whether or not the sequence is compatible with
  an implementation of quickSort.  You can run it as
   
    % /c/cs223/Hwk4/Tests/xQuick.pl /c/cs223/Hwk4/Tests/f007
   
  (where Tests/f007 can be replaced by any other file with
  unique lines).
   
  The tool is VERY fragile, so before trying it make sure
  that your Qsort can correctly sort the file, e.g., by
  running
   
    % ./Qsort /c/cs223/Hwk4/Tests/f007 | sort -c
   
  Please let me know if your Qsort works but xQuick.pl
  says that it is not quickSort.  Having examples where it
  fails will help in debugging.  Thanks.

--Stan-