CSC122F2021Lab5 < CenterForComputing

---+ Searching and sorting analysis lab
---++ Learning Objective(s)
   1 Thoroughly understand sequential search, binary search, an n^2 sort, merge sort, heap sort, and binary search tree
   1 See the implications of Big O on real data, esp. on large amounts of data
   1 Learn to write a quality report analyzing amount of work.
---++ Overview of the problem

You are to implement a number of search and sorts and then do an analysis of the work done and write a resulting report
---++ Specifics
   * For this task, you are reading a file of integers (one per line) as the data being searched. You can assume that there will be no more than 1,000,000 numbers in the file.
   * A second file will continue another list of integers that you search to see if each number if in the first list.
   * The files are specified via command line arguments with the first argument being the data to be possibly sorted and searched. The second argument is the list of numbers to be searched for.
   * Searches
      * implement a sequential search on unordered data
      * implement a binary search on ordered data
      * implement a search on a binary search tree
  * Sorts
      * implement a n^2 sort of your choice (selection, insertion, bubble)
      * implement the merge sort
      * implement the heap sort
      * implement the add to the binary search tree. It is recommended that you use a linked implementation here
   * Tasks:
      * Load the data into an array.
      * For the sequential search on unordered data, report the number of compares it takes to look up each number and the total number of compares it takes to look up all numbers (using the second file)
      * For the binary search tree, report the number of compares and moves (or swaps) it takes to build the binary search tree. Then report the number of compares it takes to look up each number and the total number of compares it takes to look up all numbers (using the second file).
      * For each sort, sort the data from the first files and report the number of compares and moves (or swaps -> be consistent when possible).  Then report the number of compares it takes to look up each number and the total number of compares it takes to look up all numbers (using the second file).
   * Run the tasks on a decent number of cases including:
      * data that is almost in order
      * data that is almost in reverse order
      * data that is in random order
      * tiny amount of data in the first file (< 100)
      * small amount of data in the first file
      * medium amount of data in the first file
      * large amount of data in the first file
      * a few numbers in the second file
      * a medium number of numbers in the second file
      * a large number of numbers in the second file
   * Number of classes
      * the file(s) that contain the code to sort and search can do <b>no</b> I/O.  Therefore you will need at least two different classes.
      * it is recommended but not required that you consider a separate class for each sort.  If you choose not to, make sure you employ quality loose coupling!
---++ Design components
   * Indicate where you are counting the compares and moves
   * Be sure to provide ways to get back the number of compares and the number of moves
   * Spend effort on your testing data
   * For this implementation, your tree can know that it is storing integers if you wish but you may also keep it independent.
---++Report
   * 
---++ Optional improvements
   * Implement a sort not covered in class
This topic: CenterForComputing > WebHome > SyllabiFall2021 > CSC122SylF2021 > CSC122F2021Lab5
Topic revision: r1 - 2021-10-19 - cathybareiss