Just search or sort then search?

Learning Objective(s)

1. Implement an n^2 sort
2. Implement the sequential and binary search
3. Confirm Big O of your searches
4. Confirm Big O of your sort
5. Use analysis to make decisions about what to code

Overview of the program

The job is to do a number of searches on a set of data. When is it better to just search? When is it worth it to sort the data and then do you searches?

Details

• You are to use integers for the numbers being searched and being searched for
• You are provided a shell that will generate the numbers (in a few different ways) and help organize the rest of your code
• Allow for up to 10,000,000 items in each array.
• Write a sequential search that will return the number of compares instead of the location of the item
• Write a binary search that will return the number of compares instead of the item
• Write a method to sort the data. You are to implement either the selection sort, insertion sort, or bubble sort. Modify it to track and return the number of compares.
• Make sure your code works. You should be able to correctly count the number of compare it takes to search an unordered list. You should also be able to count the number of compares it takes to first sort a list and then look up a number using a binary search.
• Once your code works, you are to experiment with it until you find out how many numbers need to be searched for to make the extra effort of sorting the data worthwhile. This is to be discussed in your lesson learned section of your report (which will be worth at least 20 points).
• Your testing report should include
  • enough data to justify that your code works and
  • enough data to justify your lessons that you learned.
• A small sample graph is included as a pdf in the lab folder.
• The program should be called SearchSort

Sample output: Your output may vary.

Output can be seen by running the solution

Submission

1. Create your SDR.
   • In Lessons Learned, you need to include a discussion as to when you should just search and when you should sort first. Be sure to be accurate. A graph could be very helpful.
   • Also in Lessons Learned, explain the generateDesc algorithm
   • Your testing report need not list the arrays generated. Just different cases for the sizes of the two arrays and type of data. Your expected result should not be accurate but involve big O (and actually have approximate numbers)
   • If you used any hints, be sure to indicate that in the Outside Resources Used section
2. Convert your SDR into a pdf document
3. Create an empty zip folder
4. Place all 4 java files and pdf document in it.
5. Include any testing input files you used
6. Submit the zip folder on canvas

Hints

No hints this time.

Optional improvements

1. Implement all three sorts and compare the amount of work each does (including the swaps). Confirm that your numbers correspond to the Big O we discussed in class. It should also track the number of swaps. This means that each sort should return an array of 2 integers. One would be the number of compares and one would be the number of swaps/moves.