(r1) CSC121S2022Lab10 < CenterForComputing

Tags: view all tags
---+ Tenth lab: Should I sort before searching?
---++ Learning Objective(s)
   1 Implement the binary search and a sort
   1 Start to develop skills in using Big O analysis
---++ Overview of the program
You are to implement  two searches and one sort and count the amount of work each does.  Then run it with a number of different data sets to determine when one should just search (without sorting) vs. sort first and then search.
---++ Details
   * <b>Lessons Learned</b> will be VERY important and worth 20 points.  This is where you will discuss your work and do your analysis.  Take it seriously!  Doing a lot of searches will eventually make it worth while to sort first.  When does that happen?
   * A program is provided that will generate lists of integers and save it to a file.  Take advantage of it!
   * Your program should implement:
      * Sequential search on unordered data (not from the web)
      * Recursive binary search on ordered data (not from the web)
      * Selection or insertion sort (via the specific algorithm we cover in class -> not something you found on the web!)
   * Because these are very well known and used algorithms, you can easily find this code on the web.  <b>DO NOT DO THAT</B>.  You may ONLY use class notes, class examples, previous code you have written, the textbooks from class, the assistants (Micah and Jonathan) and your classmates. Use of anything else will be consider cheating!
   * Count the number of comparisons in each algorithm
   * The two files are to be specified at the command line.  The first is the list of numbers to be search (and maybe sorted).  The second is the list of number of to searched for.
   * The program should be called *Analysis*
   * You need to have at least one method besides the main method.
   * You must use arrays as your primary storage
   * All normal exceptions should be handled (not thrown)
---++ Example of first file
<pre>
5
20
14
3
</pre>
---++ Example of second file
<pre>
5
21
14
</pre>
---+++Sample output (wording can vary)
<pre>
Without sorting it to a total of 8 compares to look up 3 numbers.
To sort and then search it took a total of 10 compares to look up 3 numbers.
</pre>
---++ Submission
   1 Create an empty zip folder.
   1 Place your program (.java file) in it
   1 Place your software development report in it.
   1 Submit the zip folder on canvas
---++ Optional improvements
   * Also implement the merge sort, heap sort, or radix sort.  You may find an algorithm (but not the code!).  Compare that sort to either the selection sort or insertion sort.
Topic revision: r1 - 2022-03-11 - cathybareiss