Students will be able to conduct a comparison study of the performance of searching algorithms, by implementing an experiment to compare the running times of well-known searching algorithms.
Design and implement an experiment to compare in real time the running times of the following searching algorithms:
An implementation of quicksort is given in a separate file (you are required to use it to sort the data in the sorted and binary searches). Time the searching algorithms several times each, and save the results in a .csv file that can be open in an Excel file later. Format your .csv file as follows:
< value of n>, < binary search time>,, < sorted search time >
< value of n>, < binary search time>,, < sorted search time >
< value of n>, < binary search time>,, < sorted search time >
< value of n>, < binary search time>,, < sorted search time >
< value of n>, < binary search time>,, < sorted search time >
...
For example (the numbers are not taken from a real example; they are offered to illustrate the content of the file)
100 165448 5553 85531
200 635102 6291 170288
300 1475774 9324 60707
400 457126 12153 63218
500 626482 18096 92991
All of the data (array values and search values) should be randomly generated using the method nextInt() from the java.util.Random class. Time not less than 5000 runs of these algorithms (i.e. your .csv file should have, at least, that number of lines). To time your code use System.nanoTime().
Use Excel to depict graphically the results of your experiment.
What did you observe?
The assignment is to be completed individually or in teams of two students. The given problem is based on the content studied in class on searching algorithms. You are allowed to use all of the code discussed in the lectures. In those cases, make sure you properly credit its source.
Students are required to structure the code as indicated in the UML class diagram: see image.