Introduction to Computer Science

You have learned two searching algorithms (binary search and sequential search) and three sorting algorithms (selection sort, insertion sort and merge sort).

In this assignment you will apply your knowledge of these algorithms. The assignment is divided in three parts.

Part 1.

Brief review on all the algorithms, log into Gradescope and submit questions 1 through 5.

Part 2.

Imagine that a programmer has made a program that allows you to generate or take arrays as inputs, and apply searching and sorting algorithms on the array. However, the programmer did not name any of the sorting methods, and it is up to you to come up with a plan to match selection sort, insertion sort and merge sort to the 3 provided sorting algorithms. In the program given to you, each sorting algorithm not only will sort the array, it will also gives you how much time is used for it to run. 

Knowing that, and the properties of the 3 sorting algorithms, try to design a testing strategy to help you identify selection sort, insertion sort and merge sort among the 3 provided algorithms.

Hint: perhaps you can identify an algorithm by simply checking the space efficiency of it, but this strategy will not work for all of them. You should think about in what situation each sorting algorithm will have the best/worst run time; and how would other algorithm handle the same test case.

It could be helpful to create a table where for each algorithm you note:

• • input array description
  • input array size
  • running time
  • space consumption
  • which algorithm you suspect this is

Download

The program is called SortDetective, download the SortDetective.class here.

Execute

To execute type: java SortDetective

NOTE: once you execute SortDetective you will have a few options to input the array to be searched or sorted. One of the options is a file which contains integers (items of the array) separated by a space.

Part 3.

Identify algorithms, log into Gradescope and submit question 6.