Description
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 arra
- 2. Linear search over sorted arra
- 3. Binary search over sorted arra
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()