You will be given a version of the Movies program (that you did for program 1) where the movies library is implemented as a linked list of movie pointers instead of an array of moivie pointers. You will add a function for the following search & sort algorithms: linear search, binary search, bubble sort, insertion sort, insertion sort descending, selection sort, merge sort, and quick sort. Some of these functions will require a swap function in the LinkedList class as well. Create a function called algorithmAnalysis that will use a timer to time how long it takes to run the algorithm on a linked list of movies and print out the times. Several movie text files will be provided for you in order for you to test your program.

MOVIES CLASS Create the functions described below. All of the following functions except for algorithmEfficiency() should be made private. o linearSearch This function should search for a particular movie title to see if it is in the list. It should return -1 if the Movie title could not be found. Use the linear search algorithm to implement this function. o binarySearch - This function should search for a particular movie title to see if it is in the list. It should return -1 if the Movie title could not be found. Use the binary search algorithm to implement this function. o bubbleSort This function should sort the LinkedList of Movies in ascending order by Movie title. This function will call a function called swap in the linkedList class to swap values in the linked list when necessary. Use the bubble sort algorithm to implement this function. o insertionSort - This function should sort the LinkedList of Movies in ascending order by Movie title. This function will call a function called swap in the linkedList class to swap values in the linked list when necessary. Use the insertion sort algorithm to implement this function. o insertionSortDescending This function should be the same as insertionSort except it will sort the LinkedList of Movies in descending order by Movie title instead of ascending order. o selectionSort - This function should sort the LinkedList of Movies in ascending order by Movie title. This function will call a function called swap in the linkedList class to swap values in the linked list when necessary. Use the selection sort algorithm to implement this function. o mergeSort & merge These two functions work together to implement the merge sort algorithm, which should sort the LinkedList of Movies in ascending order by Movie title. The mergeSort function is a recursive function which calls the merge function. The merge function dynamically allocates a new linked list of Movie pointers to use as the merged linked list. At some point in the merge function you will need to replace a node.you will do this by deleting the node (deleteNode) at a particular position and then inserting a new node (insertNode function) at a particular position. quickSort & partition These two functions work together to implement the quick sort algorithm, which should sort the LinkedList of Movies in ascending order by Movie title. The quicksort function is a recursive function which calls the partition function. The partition function will use a pivot string (c-string). The partition function will call a function called swap in the linkedList class to swap values in the linked list when necessary. o algorithmAnalysis- This is the driver function that will call all of these other functions to test the efficiency of each one. Here is the pseudocode for this function below: 1. Start timer Call linearSearch sending a temporary Text* with a c-string named Llama to it. (I dont care if It finds this string or not) Stop timer Print out total time for this algorithm 2. Start timer Call binarySearch() sending a temporary Text* with a c-string named Llama to it. Stop timer Print out total time for this algorithm 3. Call insertionSortDescending() to put linked list in opposite order. Start timer Call bubbleSort() Stop timer Print out total time for this algorithm 4. Call insertionSortDescending() to put linked list in opposite order. Start timer Call selectionSort() Stop timer Print out total time for this algorithm 5. Call insertionSortDescending() to put linked list in opposite order. Start timer Call insertionSort() Stop timer Print out total time for this algorithm 6. Start timer Call insertionSortDescending() Stop timer Print out total time for this algorithm 7. Start timer Call mergeSort() sending 0 and the length of the linked list (# of nodes) minus 1 to the function Stop timer Print out total time for this algorithm 8. Start timer Call quickSort() sending 0 and the length of the linked list (# of nodes) minus 1 to the function Stop timer Print out total time for this algorithm

below are and moveis.H

//movies.h

#ifndef MOVIES_H #define MOVIES_H

#include "Movie.h" #include "LinkedList.h" #include #include #include

using namespace std;

class Movies { private: LinkedList *movieList; //Movie** moviesArray; //an array of pointers - each pointer points to a single Movie //int maxMovies; //maximum number of elements in the array //int numMovies; //current number of movies in the array public: /* Function name: Movies constructor Parameters: An integer containing the maximum size of the movie library Purpose: This function is automatically called when a Movies object is created and it creates a library of movies. The function will dynamically allocate a movies array based on the maximum size and will also set the current number of movies to zero. */ Movies(); /* Function name: ~Movies destructor Purpose: This function is automatically called when the Movies object is destroyed. This releases the dynamically created individual movies and then deletes the array. */ ~Movies();

/* Function name: addMovieToArray Parameters: none Returns: A boolean indicating if the movie was able to be added or not Purpose: This function should be called when you need to add a single movie to the movie library. */ void addMovieToList(); void insertionSort(); int binarySearch(int, int, Text*);

/* Function name: displayMovies Parameters: none Returns: none (void) Purpose: This function should be called when the user wants to have all the movies in the library printed to the screen. */ void displayMovies();

/* Function name: displayMovieTitles Parameters: none Returns: none (void) Purpose: This function should be called when you want to print only the movie titles out of the movie library */ void displayMovieTitles();

/* Function name: readMoviesFromFile Parameters: A pointer to a character (c-string or string literal argument) containing the filename Returns: none (void) Purpose: This function should be called when the user wants to read movie data from a file and add the movies to the movie library. The file must have data in the following order: title, length, year, genre, rating, number of Oscars won, star rating */ void readMoviesFromFile(char* filename);

/* Function name: removeMovieFromList Parameters: none Returns: none (void) Purpose: This function should be called when the user wants to remove one single movie from the movie library. The movie to be removed must is identified by the user and then removed. */ void removeMovieFromList();

/* Function name: editMovieInList Parameters: none Returns: none Purpose: This function should be called when you need to edit a movie in the list */ void editMovieInList(); /* Function name: saveToFile Parameters: A pointer to a character (c-string or string literal argument) containing the filename Returns: none (void) Purpose: This function should be called when the user wants to print all the movie data from the movie library to a file. The data is printed in the following order (one piece of data per line): title, length, year, genre, rating, num oscars won, star rating */ void saveToFile(char *filename);

//accessor functions to get the attribute values int getNumMovies() const; };

#endif