Just search or sort then search?

Learning Objective(s)

1. Implement a an n^2 sort
2. Confirm Big O of your sort
3. 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
• The naming of your methods is very important.
• Allow for up to 10,000,000 items in each array.
• Use your method from last week to generate an array of random numbers
• Use your method from last week to do the sequential search on unordered data. Modify it to return the number of compares used instead of the location of item.
• Use one of your methods from last week for the binary search. (You may choose either). Modify it to return the number of compares used instead of the location 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.
• The program should be called SearchSort

Sample dialogue (data results may not be accurate). Your dialogue may vary. It could be a lot shorted.

How big of an array to you want to search? 1000
What is the range of the data you want to search?1 9999
How many numbers o you want to search for? 20
It took 9878 comparisons to look up all 20 numbers (ranging from 1 to 9999) in a random array of 1000 numbers (in the same range).
It took 15000 comparisons to sort the 1000 pieces of data.
It took 200 comparisons to look up all 20 numbers (same range) in the sorted list (of 1000 numbers).

Submission

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

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.