In this assignment, you will create a program that allows the user to choose bet
ID: 3571597 • Letter: I
Question
In this assignment, you will create a program that allows the user to choose between the following menu choices (menu-driven program):
1. Linear Search
2. Binary Search
3. Bubble Sort
4. Selection Sort
5. Quit
Keep running the program until the user chooses to Quit. Your program should have the following parts:
Searching Algorithms (Linear and Binary Search)
You are the owner of a book store. You have the following information available in your stock (information is stored in the form of parallel arrays): String[] bookTitle = {“Starting out with Java”, “Java Programming”, “Software Structures”, “Design and Analysis of Algorithms”, “Computer Graphics”, “Artificial Intelligence: A Modern Approach”, “Probability and Statistics”, “Cognitive Science”, “Modern Information Retrieval”, “Speech and Language Processing”}; int[] bookID = {1101, 1211, 1333, 1456, 1567, 1642, 1699, 1755, 1800, 1999}; double[] bookPrice = {112.32, 73.25, 54.00, 67.32, 135.00, 173.22, 120.00, 42.25, 32.11, 123.75}; First display() the above information to the user in a tabular format, using a void method. Your program should then ask for the book ID and the number of books the user wishes to purchase. Based on the book ID provided by the user, display the following information (if the ID is found):
o Book ID
o Book Title
o Number of books bought
o Total cost of the purchase
If the book ID is not found, display a message saying so. The book ID needs to be searched based on linearSearch() or binarySearch() (based on user choice from the menu).
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. Use bubbleSort() or selectionSort() (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 following functions: • display(): To display the contents of parallel array in a tabular format. Take in the three different arrays as parameters. • linearSearch(): To apply the linear search algorithm to search for the book ID. Returns the index position, or -1 if not found • binarySearch(): To apply the binary search algorithm to search for the book ID. Returns the index position of the found book ID, or -1 if not found. • bubbleSort(): To apply the bubble sort algorithm to sort the elements of an unsorted array
• selectionSort(): To apply the selection sort algorithm to sort the elements of an unsorted 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 should validate (input validation) the menu choice entered by the user, and force them to reenter a menu choice if their original input was invalid.
A bonus programming part has been provided below for extra points.
Bonus Part (Optional): 20 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 seconds) required for each of the Searching and Sorting techniques. Execution time is calculated from the start of a function call to the end of the function. Look up online resources on how to calculate elapsed time and using the system time library. 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)?
Explanation / Answer
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;
public class Chegg2 {
public static void main(String args[])throws IOException
{
Chegg2 obj=new Chegg2();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int no_of_books;
Random rand=new Random();
String[] bookTitle = {"Starting out with Java", "Java Programming", "Software Structures",
"Design and Analysis of Algorithms", "Computer Graphics", "Artificial Intelligence: A Modern Approach",
"Probability and Statistics", "Cognitive Science", "Modern Information Retrieval", "Speech and Language Processing"};
int[] bookID = {1101, 1211, 1333, 1456, 1567, 1642, 1699, 1755, 1800, 1999};
double[] bookPrice = {112.32, 73.25, 54.00, 67.32, 135.00, 173.22, 120.00, 42.25, 32.11, 123.75};
boolean flag=true;
System.out.println(" Please select an option: ");
System.out.println("-------------------------");
System.out.println("1. Linear Search");
System.out.println("2. Binary Search");
System.out.println("3. Bubble Sort");
System.out.println("4. Selection Sort");
System.out.println("5. Quit");
try{
int input=Integer.parseInt(br.readLine());
if(input>5 || input<1)
{
flag=false;
while(flag==false)
{
System.out.println(" Please select a valid option: ");
System.out.println("-------------------------");
System.out.println("1. Linear Search");
System.out.println("2. Binary Search");
System.out.println("3. Bubble Sort");
System.out.println("4. Selection Sort");
System.out.println("5. Quit");
input=Integer.parseInt(br.readLine());
if(input<=5 && input>=1)
flag=true;
}
}
while(input!=5)
{
switch(input){
case 1: obj.displayDetails(bookTitle,bookID,bookPrice);
System.out.println(" Please Enter the book id you wish to purchase: ");
int id=Integer.parseInt(br.readLine());
long startTime=System.nanoTime();
int index1=obj.linearSearch(id, bookID.length, bookID);
System.out.println("Time taken for Linear Search :-"+(System.currentTimeMillis()-startTime)+" nanoseconds");
if(index1!=-1){
System.out.println("Please Enter the number of books you wish to purchase: ");
no_of_books=Integer.parseInt(br.readLine());
obj.calculateTotal(bookTitle[index1], id, bookPrice[index1]*no_of_books,no_of_books);
}
else
{
System.out.println("Invalid book ID provided");
System.exit(0);
}
break;
case 2: obj.displayDetails(bookTitle,bookID,bookPrice);
System.out.println(" Please Enter the book id you wish to purchase: ");
int iden=Integer.parseInt(br.readLine());
long startTime2=System.nanoTime();
int index=obj.binarySearch(iden, bookID.length, bookID);
System.out.println("Time taken for Binary Search :-"+(System.currentTimeMillis()-startTime2)+" nanoseconds");
if(index!=-1){
System.out.println("Please Enter the number of books you wish to purchase: ");
no_of_books=Integer.parseInt(br.readLine());
obj.calculateTotal(bookTitle[index], iden, bookPrice[index]*no_of_books,no_of_books);
}
else
{
System.out.println("Invalid book ID provided");
System.exit(0);
}
break;
case 3: int randomArray[]=new int[10];
int sortedArray[]=new int[10];
//print array before sorting using bubble sort algorithm
System.out.println("Array Before Bubble Sort:");
for(int i=0; i <10; i++){
randomArray[i]=rand.nextInt(500);
System.out.print(randomArray[i]+ " ");
}
//sort an array using bubble sort algorithm
long sortTimer=System.nanoTime();
sortedArray=obj.bubbleSort(randomArray);
System.out.println("Time taken for Bubble Sort :-"+(System.currentTimeMillis()-sortTimer)+" nanoseconds");
System.out.println("");
//print array after sorting using bubble sort algorithm
System.out.println(" Array After Bubble Sort:");
for(int i=0; i < sortedArray.length; i++){
System.out.print(sortedArray[i] + " ");
}
break;
case 4: int randArray[]=new int[10];
int sortArray[]=new int[10];
//print array before sorting using bubble sort algorithm
System.out.println("Array Before Selection Sort:");
for(int i=0; i <10; i++){
randArray[i]=rand.nextInt(500);
System.out.print(randArray[i]+ " ");
}
//sort an array using selectionSort algorithm
long sortTimer2=System.nanoTime();
sortArray=obj.selectionSort(randArray);
System.out.println("Time taken for Selection Sort :-"+(System.currentTimeMillis()-sortTimer2)+" nanoseconds");
System.out.println("");
//print array after sorting using selectionSort algorithm
System.out.println(" Array After Selection Sort:");
for(int i=0; i < sortArray.length; i++){
System.out.print(sortArray[i] + " ");
}
break;
}
break;
}
}
catch(NumberFormatException ex)
{
System.out.println("Invalid Input Format");
System.exit(0);
}
}
public void displayDetails(String bookTitle[],int bookID[],double bookPrice[])
{
System.out.println(" Book Title | BookId | BookPrice");
System.out.println("--------------------------------------------------------------------------------------------------------");
for(int i=0;i<bookID.length;i++){
if(bookID[i]==1456)
System.out.println(bookTitle[i]+" "+bookID[i]+" "+bookPrice[i]);
else if(bookID[i]==1642)
System.out.println(bookTitle[i]+" "+bookID[i]+" "+bookPrice[i]);
else if(bookID[i]==1699)
System.out.println(bookTitle[i]+" "+bookID[i]+" "+bookPrice[i]);
else if(bookID[i]==1800)
System.out.println(bookTitle[i]+" "+bookID[i]+" "+bookPrice[i]);
else if(bookID[i]==1999)
System.out.println(bookTitle[i]+" "+bookID[i]+" "+bookPrice[i]);
else
System.out.println(bookTitle[i]+" "+bookID[i]+" "+bookPrice[i]);
}
}
public void calculateTotal(String title,int id,double price,int quantity)
{
System.out.println(" Book Title | BookId | quantity | BookPrice");
System.out.println("---------------------------------------------------------------------------------------------------------------------------------------------");
if(id==1456)
System.out.println(title+" "+id+" "+quantity+" "+price);
else if(id==1642)
System.out.println(title+" "+id+" "+quantity+" "+price);
else if(id==1699)
System.out.println(title+" "+id+" "+quantity+" "+price);
else if(id==1800)
System.out.println(title+" "+id+" "+quantity+" "+price);
else if(id==1999)
System.out.println(title+" "+id+" "+quantity+" "+price);
else
System.out.println(title+" "+id+" "+quantity+" "+price);
}
public int[] bubbleSort(int intArray[])
{
int n = intArray.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(intArray[j-1] > intArray[j]){
//swap the elements!
temp = intArray[j-1];
intArray[j-1] = intArray[j];
intArray[j] = temp;
}
}
}
return intArray;
}
public int[] selectionSort(int intArray[])
{
for (int i = 0; i < intArray.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < intArray.length; j++){
if (intArray[j] < intArray[index]){
index = j;//searching for lowest index
}
}
int smallerNumber = intArray[index];
intArray[index] = intArray[i];
intArray[i] = smallerNumber;
}
return intArray;
}
public int binarySearch(int element,int n,int array[])
{
int value=0;
int first = 0;
int last = n - 1;
int middle = (first + last)/2;
while( first <= last )
{
if ( array[middle] < element )
first = middle + 1;
else if ( array[middle] == element )
{
value=(middle);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if ( first > last )
value= -1;
return value;
}
public int linearSearch(int element,int n,int array[])
{
int value=-1;
for(int i=0;i<n;i++)
{
if(array[i]==element)
value=i;
}
return value;
}
}
/*As answer to your question binary search is better and faster. also Bubble sort is much better sorting techniques as comapred to selection sort on basis of time complexity.*/