Program Specification
You will add three sorting methods to assignment 4, the MovieCollection class. The methods will be:
• public void sortByName() – Sort the movies in your collection from a – z. Use selection sort.
• public void sortByTomatoScore() – Sort the movies by tomato score from best to worst. Use insertion sort.
• public void sortByLength() – Sort movies from shortest to longest based on runtime. Use either sorting algorithm.
You will also be implementing a few methods in the binarySearch.java file provided. The main method and display method are provided. The main method creates two arrays, one which will hold a random collection of ints, which you will randomize, and another which will hold a collection of ints sorted in increasing order.
The main method performs 3 searches.
1. Linear search over unsorted array.
2. Linear search over sorted array.
3. Binary search over sorted array.
We do not perform binary search on an unsorted array because binary search requires the array to be sorted. It is a trade off for having faster search times.
Below is a list of methods you will have to implement.
• public static void randomize(int[] array) – Randomly select two distinct indexes in the array and swap them. The number of swaps required will be array.length/2.
• Public static int linearSearch(int val, int[] array) – Linearly search the array for the value passed int. If the value is found, return the index you found it at. If you did not find it, return -1.
• Public static int binarySearch(int val, int[] array) – Use the binary search technique discussed in class to find the value in the array. Return the index the value is found at or return -1 if it is not found.
When complete, run the program and search for many different results. If you want to see an immediate difference, search for -1 (there are no negative numbers in the array, so which of the three searches will return first?)
Analyzing Runtimes
Using the MovieCollection class I provided plus the methods you implemented above in MovieCollection, give the Big O notation for each method listed below. Provide your answers directly in the D2L dropbox for the questions below when submitting.
Undergraduate Students – Answer questions 1 – 8.
Graduate Students – Answer all questions.
1.
MovieCollection()
___________________
2.
getTotalMovies()
___________________
3.
addMovie(Movie movie)
___________________
4.
findMovie(Movie movie)
___________________
5.
removeMovie(Movie movie)
___________________
6.
shiftCollectionLeft(int index)
___________________
7.
moviesToAvoid()
___________________
8.
sortByName()
___________________
9.
removeMovieAt(int index)
___________________
10. addMovieAt(Movie movie, int index)
___________________
11. findBestMovie()
___________________
12. moviesToWatch()
___________________
13. printOutMovieList()
___________________
14. sortByTomatoScore()
___________________
15. shiftCollectionRight(int index)
___________________
16. sortByLength()
___________________
