Java

Program Specification

You will add three sorting methods to 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.

Answer questions 1 8.

1. MovieCollection()

2. getTotalMovies()

3. addMovie(Movie movie)

4. findMovie(Movie movie)

5. removeMovie(Movie movie)

6. shiftCollectionLeft(int index)

7. moviesToAvoid()

8. sortByName()

Code Provided

MovieCollection Code

public class MovieCollection {

private Movie[] movies;

private int movieCount;

public MovieCollection(){ movies = new Movie[10]; movieCount = 0; }

public int getTotalMovies(){ return movieCount;

}

public boolean addMovie(Movie movie){ if(movieCount < movies.length && findMovie(movie) == -1){ movies[movieCount++] = movie; return true; } return false; }

public boolean addMovieAt(Movie movie, int index){

if(index >= 0 && index <= movieCount && movieCount < 10 && findMovie(movie) == -1){ shiftCollectionRight(index); movies[index] = movie; movieCount++; return true; } return false; }

private void shiftCollectionRight(int index) { for(int i = movieCount; i > index; i--){ movies[i] = movies[i-1]; } }

public int findMovie(Movie movie){ for(int i = 0; i < movieCount; i++){ if(movies[i].equals(movie)){ return i; } } return -1; }

public Movie getMovieAt(int index) {

if(index >= movieCount || index < 0) { return null; }

return movies[index];

}

public boolean removeMovie(Movie movie){ int index = findMovie(movie); if(index != -1){ shiftCollectionLeft(index); return true; } return false; }

public Movie removeMovieAt(int index) {

if(index >= movieCount || index < 0) { return null; }

Movie movieToReturn = movies[index]; shiftCollectionLeft(index); return movieToReturn;

}

private void shiftCollectionLeft(int index){ for(int i = index; i < movieCount-1; i++){ movies[i] = movies[i+1]; } --movieCount; }

public Movie findBestMovie(){ if(movieCount == 0){ return null; } else { Movie favorite = movies[0]; for(int i = 0; i < movieCount; i++){ if(favorite.getTomatoScore() < movies[i].getTomatoScore()){ favorite = movies[i]; } } return favorite; } }

public void moviesToAvoid(){ int counter = 1; System.out.println("Movies to avoid: "); for(int i = 0; i < movieCount; i++){ if(!movies[i].isFresh()){ System.out.println("Movie " + counter++ + ": "); System.out.println(movies[i]); System.out.println(); } } }

public void moviesToWatch(){ int counter = 1; System.out.println("Movies to watch: "); for(int i = 0; i < movieCount; i++){ if(movies[i].isFresh()){ System.out.println("Movie " + counter++ + ": "); System.out.println(movies[i]); System.out.println(); } } }

public void printOutMovieList(){ System.out.println("All of my movies: "); for(int i = 0; i < movieCount; i++){ System.out.println("Movie " + (i+1) + ": " + movies[i].getName()); } System.out.println(); }

/** * Sort movies by name going from A-Z. * You may use any method you like to compare Strings to help sort. * Use Selection Sort for this method. */ public void sortByName() {

//TODO

}

/** * Sort movies by tomato score from best to worst. * Use Insertion Sort for this method. */ public void sortByTomatoScore() {

//TODO

}

/** * Sort movies by runtime, ie their length, from shortest to longest. * Use either sorting method for this method. */ public void sortByLength() {

//TODO

}

}

-------------------------

BinarySearch Code

import java.util.Scanner;

public class BinarySearch {

public static void main(String[] args) {

Scanner scr = new Scanner(System.in);

System.out.println("Starting Program and initializiing arrays.");

//IF your computer takes a very long time to create the arrays, you may decrease the size a little int size = 100000000;

int[] unsortedArray = new int[size]; int[] sortedArray = new int[size];

for(int i = 0; i < unsortedArray.length; i++) { unsortedArray[i] = i; sortedArray[i] = i; }

System.out.println("Starting to randomize. This may take several seconds."); randomize(unsortedArray);

String input = ""; long start, totalTime; int val, index;

while(!input.equals("quit")) {

System.out.print("Please enter a number to search for (between 0 and " + (size-1) + "): ");

input = scr.nextLine();

if(input.equals("quit")) { continue; }

val = Integer.parseInt(input);

start = System.nanoTime(); index = linearSearch(val , unsortedArray); totalTime = System.nanoTime() - start; displayResults(val,index,totalTime, "linear unsorted");

start = System.nanoTime(); index = linearSearch(val , sortedArray); totalTime = System.nanoTime() - start; displayResults(val,index,totalTime, "linear sorted");

start = System.nanoTime(); index = binarySearch(val , sortedArray); totalTime = System.nanoTime() - start; displayResults(val,index,totalTime, "binary search");

System.out.println();

}

scr.close(); System.out.println("Goodbye.");

}

public static void displayResults(int val, int index, long totalTime, String searchStyle) {

if(searchStyle.equals("linear unsorted")) { System.out.println(" Linear Unsorted Search Results:"); } else if (searchStyle.equals("linear sorted")) { System.out.println(" Linear Sorted Search Results:"); } else { System.out.println(" Binary Search Results:"); }

if(index == -1) { System.out.println("The number <" + val +"> was not found. It took " + totalTime + " to search."); } else { System.out.println("The number <" + val +"> was found at index <" + index + ">. It took " + totalTime + " nano seconds to search."); } }

/** * Randomly select two different indices in the array and swap them. * If your array size is n, perform n/2 swaps. * * @param array */ public static void randomize(int[] array) {

//TODO

}

/** * Search the array for the passed in val using a sequential search. * Return the location of val when found. * If it isn't found return -1. * * @param val * @param array * @return index or -1 */ public static int linearSearch(int val, int[] array) {

//TODO

}

/** * Search the array for the passed in val using binary search. * Return the location of val when found. * If it isn't found return -1. * * @param val * @param array * @return */ public static int binarySearch(int val, int[] array) {

//TODO

}

}

-----------

JUnit Code import static org.junit.Assert.*;

import org.junit.After; import org.junit.Before; import org.junit.Test;

public class JUnit {

MovieCollection f;

@Before public void setUp() { f = new MovieCollection(); }

Movie crazyRichAsians = new Movie("Crazy Rich Asians",120,93); Movie oceans8 = new Movie("Oceans 8",110,68); Movie happytimeMurders = new Movie("The Happytime Murders",91,22); Movie fallout = new Movie("Mission Impossible: Fallout",147,97); Movie slenderMan = new Movie("Slender man",93,7); Movie bigSick = new Movie("The Big Sick",119,98); Movie mile22 = new Movie("Mile 22",90,22); Movie fallenKingdom = new Movie("Jurassic World: Fallen Kingdom",129,49); Movie wonderWoman = new Movie("Wonder Woman",141,93); Movie goodfellas = new Movie("Goodfellas",146,96); Movie quietPlace = new Movie("A Quiet Place", 90, 95);

@After public void tearDown(){ f = null; }

@Test public void testSorting() {

f.addMovie(bigSick); f.addMovie(fallout); f.addMovie(oceans8); f.addMovie(quietPlace); f.addMovie(wonderWoman);

f.sortByLength();

assertEquals(0, f.findMovie(quietPlace)); assertEquals(1, f.findMovie(oceans8)); assertEquals(2, f.findMovie(bigSick)); assertEquals(3, f.findMovie(wonderWoman)); assertEquals(4, f.findMovie(fallout));

f.sortByName();

assertEquals(0, f.findMovie(quietPlace)); assertEquals(1, f.findMovie(fallout)); assertEquals(2, f.findMovie(oceans8)); assertEquals(3, f.findMovie(bigSick)); assertEquals(4, f.findMovie(wonderWoman));

f.addMovie(goodfellas); f.addMovie(slenderMan);

f.sortByTomatoScore();

assertEquals(0, f.findMovie(bigSick)); assertEquals(1, f.findMovie(fallout)); assertEquals(2, f.findMovie(goodfellas)); assertEquals(3, f.findMovie(quietPlace)); assertEquals(4, f.findMovie(wonderWoman)); assertEquals(5, f.findMovie(oceans8)); assertEquals(6, f.findMovie(slenderMan));

}

}

---------------

MovieDriver Code

public class MovieDriver {

public static void main(String [] args){

MovieCollection myMovies = new MovieCollection();

Movie crazyRichAsians = new Movie("Crazy Rich Asians",120,93); Movie oceans8 = new Movie("Oceans 8",110,68); Movie happytimeMurders = new Movie("The Happytime Murders",91,22); Movie fallout = new Movie("Mission Impossible: Fallout ",147,97); Movie slenderMan = new Movie("Slender man",93,7); Movie bigSick = new Movie("The Big Sick",119,98); Movie mile22 = new Movie("Mile 22",90,22); Movie fallenKingdom = new Movie("Jurassic World: Fallen Kingdom",129,49); Movie wonderWoman = new Movie("wonder Woman",141,93); Movie goodfellas = new Movie("Goodfellas",146,96);

myMovies.addMovie(crazyRichAsians); myMovies.addMovie(oceans8); myMovies.addMovie(happytimeMurders); myMovies.addMovie(fallout); myMovies.addMovie(slenderMan); myMovies.addMovie(bigSick); myMovies.addMovie(mile22); myMovies.addMovie(fallenKingdom); myMovies.addMovie(wonderWoman); myMovies.addMovie(goodfellas);

System.out.println("Total movies: " + myMovies.getTotalMovies()); myMovies.printOutMovieList();

System.out.println(); System.out.println("Total movies sorted by name: " + myMovies.getTotalMovies()); myMovies.sortByName(); myMovies.printOutMovieList();

System.out.println(); System.out.println("Total movies sorted by score: " + myMovies.getTotalMovies()); myMovies.sortByTomatoScore(); myMovies.printOutMovieList();

System.out.println(); System.out.println("Total movies sorted by length: " + myMovies.getTotalMovies()); myMovies.sortByLength(); myMovies.printOutMovieList();

}

}

---------

Movie Class

public class Movie {

private String name; private int minutes; private int tomatoScore;

public Movie(String name, int minutes){ this(name, minutes, 0); }

public Movie(String name, int minutes, int tomatoScore){

this.name = name; this.minutes = minutes; this.tomatoScore = tomatoScore;

}

public int getMinutes(){ return this.minutes; }

public String getName(){ return this.name; }

public int getTomatoScore(){ return this.tomatoScore; }

public void setTomatoScore(int score){ if(score >= 0 && score <= 100){ this.tomatoScore = score; } }

public boolean isFresh(){ return this.tomatoScore >= 60; }

private String convertMinutes(){ return "" + (this.minutes/60) + "hrs " + (this.minutes%60) + "min"; }

@Override public boolean equals(Object other){ if (other instanceof Movie){ Movie tmp = (Movie)other; return tmp.name.equals(this.name) && tmp.minutes == this.minutes && tmp.tomatoScore == this.tomatoScore; } return false; }

@Override public String toString(){ return "Name: " + this.name + " Length : " + convertMinutes() + " Tomato Rating : " + (isFresh() ? "Fresh" : "Rotten"); }

}