In this assignment, you will create a program that allows the user to choose between the following menu choices (menu-driven program):
- Linear Search
- Binary Search
- Bubble Sort
- Selection Sort
- Quit
Keep running the program until the user chooses to Quit. Your program will be split up intotwo main parts, where each part will run differently. ForOptions 1 and 2, you are working withsearching methodsby creating themovie storedescribed below. ForOptions 3 and 4, you are working withsorting methodsby generating 10 random numbers and then sorting it.
Searching Algorithms (Linear and Binary Search)
You are the owner of a movie store. You have the following information available in your stock (information is stored in the form of parallel arrays):
String[] movieTitle = {“Gone with the Wind”, “Star Wars”, “The Truman Show”, “The Martian”, “Blade Runner 2049”, “Dunkirk”, “Upstream Color”, “La La Land”, “The King’s Speech”, “Pirates of the Caribbean”};
int[] movieID = {110100, 121101, 133310, 145601, 156711, 164210, 169901, 175501, 180000, 199900};
double[] moviePrice = {3.32, 43.25, 54.00, 67.32, 105.00, 113.22, 20.00, 42.25, 32.11, 123.75};
int[] quantityAvailable = {11, 12, 13, 12, 14, 12, 19, 15, 18, 19};
Firstdisplay()the above information to the user in a tabular format, using a void method. Your program should then ask for the movie ID and the number of movies the user wishes to purchase. You need to check to make sure that the requested quantity is available. After every purchase, you need to update the quantityAvailable array for that particular movie. Based on the movie ID provided by the user, display the following information (if the ID is found):
o Movie ID o Movie Title o Total cost of the purchase o Quantity remaining for that title
If the movie ID is not found, display a message saying so. The movie ID needs to be searched based onlinearSearch()orbinarySearch()(based on user choice from the menu).
Note that when using binarySearch(), there is no need to manually sort for this situation, as the movie ID’s are already sorted for you.
Sorting Algorithms (Bubble and Selection Sort)
Your program should generate 10 random numbers in the range of 1 to 500 and store them in an array. UsebubbleSort()orselectionSort()(based on the menu choice) to sort the array of numbers. Display both the unsorted and the sorted array.
Instructions:Please make sure your code has the followingmethods:
- void display(String[] movieTitle, int[] movieID, double[] moviePrice):To display the contents of parallel array in a tabular format. Take in the three different arrays as parameters.
- int linearSearch(int[] movieID, int key):To apply the linear search algorithm to search for the movie ID. Returns the index position, or -1 if not found. The key parameter should be the ID the user is searching for.
- int binarySearch(int[] movieID, int key):To apply the binary search algorithm to search for the movie ID. Returns the index position of the found movie ID, or -1 if not found. The key parameter should be the ID the user is searching for.
- int[] bubbleSort(int[] unsortedArray):To apply the bubble sort algorithm to sort the elements of an unsorted array. You should pass in an unsorted array as a parameter, and return the sorted array.
- int[] selectionSort(int[] unsortedArray):To apply the selection sort algorithm to sort the elements of an unsorted array. You should pass in an unsorted array as a parameter, and return the sorted array.
You can use additional methods (optional) for other operations. Make sure your program runs until the user decides to quit the program. Your program shouldvalidate(input validation) the menu choice entered by the user, and force them to re-enter a menu choice if their original input was invalid. A bonus programming part has been provided below for extra points.
Extra Credit (Option 1): 10 points
We want to test the efficiency of our searching and sorting algorithms. To test the efficiency, calculate and display the execution (elapsed) time (in milliseconds). You need to store the time at the beginning of the execution of each sort or search algorithm. Then, you also store the time at the end of execution. The difference between these two stored times, is the execution time. You need to remember that system time is in milliseconds and you need proper formatting to display that. Also, for small datasets, the execution time will be a very small number. Make sure to show the start time, end time, and the execution time. Can you tell which searching technique is better/faster (linear search vs. binary search) and which sorting technique is better/faster (bubble sort vs. selection sort)?
Extra Credit (Option 2): 10 points
Choose one of the sorting algorithms and apply it to the movie arrays and sort them based on the quantities available from smaller to larger quantities. Remember that you need to show all the movie information including movieID, movieTitle, and moviePrice in addition to the quantityAvailable.