Tenth lab: Should I sort before searching?

Learning Objective(s)

1. Implement the binary search and a sort
2. 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

• Lessons Learned 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? Consider adding a graph (scatter plot) of your work.
• 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. DO NOT DO THAT. 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!
  • An additional resource that is allowed for this lab is : Object-Oriented Data Structures Using JAVA, Third edition by Nell Dale, Daniel Joyce and Chip Weems (Chapter 10.2 for simple sorts.)
• There are at most 200,000 numbers in the first file. There is no limit for the number of numbers in the second file.
• 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

5
20
14
3

Example of second file

5
21
14

Sample output (wording can vary)

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.

Submission

1. Create an empty zip folder.
2. Place your program (.java file) in it
3. Place your software development report in it.
4. 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.