Question

Please code by Java.

The following preemptive program with this problem after sample output(fill random number, recursive search, non-recursive search, exit), You just need to modify this code to add sorting and time calculations.

Problem Description:

Expand on Lab3 by adding methods that implement Bubble Sort, Selection Sort, Insertion Sort, Merge Sort and Quick Sort for displaying the sorted integers from the randomly generated array. NOTE: Create separate methods for each type of sort. Run Tests for all 4 types of Sorts with the same values as below. When Menu option 4 is selected, a submenu of all the five sort algorithms is displayed.

Selecting a sort option in the submenu say 'B' for for Bubble sort displays the unsorted array followed by the name of sorting algorithm with its complexity and the sorted array in that sequence as shown in the sample output further down (To get a clear picture of the requirements look at the SAMPLE OUTPUT):

B. Bubble Sort ( Simple sorting algorithm - O(n2) Complexity )
I. Insertion Sort ( Simple sorting algorithm - O(n2) Complexity )
S. Selection Sort ( Simple sorting algorithm - O(n2) Complexity )
M. Merge Sort ( Recursive Divide-And-Conquer - O(n log n) Complexity )
Q. Quick Sort ( Recursive Divide-And-Conquer - O(n log n) Complexity )
R. Return to main menu

//NOTE: the random array values will display instead of x1, x2, x2, x3, x4

Use the built-in nanotime() and currentTimeMillis() methods of the System class to determine how long each of the above sorting algorithm takes in nanoseconds and milliseconds. Time taken by each operation should be displayed on the screen. Hint: wrap each method in (a) and (b) with the timing methods.

HINTS

The secureRandom class should return an UNSORTED random array of numbers between 10 and 100.

You can create 4 copies of the unsorted data array such as bubbleArray, selectArray, insertArray, mergeArray and quickArray and pass each to its corresponding method. That way menu option 4 shows unsorted data.

Alternatively and more efficiently you can pass the unsorted array returned by SecureRandom class directly to the sorting methods.

That way methods invoked by menu option 4 receive unsorted data.

Check out the basic sorting algorithms here: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/sorting.html

Sample Output: (green is user input)

Select your option in the menu below: 1: Initialize and populate an array of 20 random integers. 2: Perform a recursive binary search. 3: Perform a non-recursive binary search. 4: Sort the array 5: Quit >1 Array of randomly generated integers: [28, 32, 73, 54, 26, 95, 25, 96, 29, 71, 98, 16, 11, 45, 32, 86, 95, 80, 95, 37]

Select your option in the menu below:
1: Initialize and populate an array of 20 random integers.
2: Perform a recursive binary search.
3: Perform a non-recursive binary search.
4: Sort the array
5: Quit
>2
Please enter an integer value to search:
>41
[28, 32, 73, 54, 26, 95, 25, 96, 29, 71, 98, 16, 11, 45, 32, 86, 95, 80, 95, 37]

45 was found at index position 13 : Recursive Binary Search

Time taken in nanoseconds: 4275900
Time taken in milliseconds: 5

Select your option in the menu below:
1: Initialize and populate an array of 20 random integers.
2: Perform a recursive binary search.
3: Perform a non-recursive binary search.
4: Sort the array
5: Quit
>3
Please enter an integer value to search:
>41
[28, 32, 73, 54, 26, 95, 25, 96, 29, 71, 98, 16, 11, 45, 32, 86, 95, 80, 95, 37]

45 was found at index position 13 : Iterative Binary Search

Time taken in nanoseconds: 18155500
Time taken in milliseconds: 18

Select your option in the menu below:
1: Initialize and populate an array of 20 random integers.
2: Perform a recursive binary search.
3: Perform a non-recursive binary search.
4: Sort the array - Go to submenu
5: Quit

>4

Select a sorting algorithm to sort the data array

B. Bubble Sort
I. Insertion Sort
S. Selection Sort
M. Merge Sort
Q. Quick Sort

X. Return to Main Menu

>B

[28, 32, 73, 54, 26, 95, 25, 96, 29, 71, 98, 16, 11, 45, 32, 86, 95, 80, 95, 37]

Bubble Sort: Simple sorting algorithm - O(n2) Complexity

[11, 16, 26, 25, 28, 29, 32,32, 37, 45, 54, 71, 73, 80, 86, 95, 95, 95, 96, 98]

Time taken in nanoseconds: 15155500
Time taken in milliseconds: 68

Select a sorting algorithm to sort the data array

B. Bubble Sort
I. Insertion Sort
S. Selection Sort
M. Merge Sort
Q. Quick Sort
R. Return to Main Menu

>I

[28, 32, 73, 54, 26, 95, 25, 96, 29, 71, 98, 16, 11, 45, 32, 86, 95, 80, 95, 37]

Insertion Sort: Simple sorting algorithm - O(n2) Complexity

[11, 16, 26, 25, 28, 29, 32,32, 37, 45, 54, 71, 73, 80, 86, 95, 95, 95, 96, 98]

Time taken in nanoseconds: 28155500
Time taken in milliseconds: 48

Select a sorting algorithm to sort the data array

B. Bubble Sort
I. Insertion Sort
S. Selection Sort
M. Merge Sort
Q. Quick Sort
R. Return to Main Menu

>S

[28, 32, 73, 54, 26, 95, 25, 96, 29, 71, 98, 16, 11, 45, 32, 86, 95, 80, 95, 37]

Selection Sort: Simple sorting algorithm - O(n2) Complexity

[11, 16, 26, 25, 28, 29, 32,32, 37, 45, 54, 71, 73, 80, 86, 95, 95, 95, 96, 98]

Time taken in nanoseconds: 21155500
Time taken in milliseconds: 38

Select a sorting algorithm to sort the data array

B. Bubble Sort
I. Insertion Sort
S. Selection Sort
M. Merge Sort
Q. Quick Sort
R. Return to Main Menu

>M

[28, 32, 73, 54, 26, 95, 25, 96, 29, 71, 98, 16, 11, 45, 32, 86, 95, 80, 95, 37]

Merge Sort: Recursive Divide-And-Conquer - O(n log n) Complexity

[11, 16, 26, 25, 28, 29, 32,32, 37, 45, 54, 71, 73, 80, 86, 95, 95, 95, 96, 98]

Time taken in nanoseconds: 9155500
Time taken in milliseconds: 14

Select a sorting algorithm to sort the data array

B. Bubble Sort
I. Insertion Sort
S. Selection Sort
M. Merge Sort
Q. Quick Sort
R. Return to Main Menu

>Q

[28, 32, 73, 54, 26, 95, 25, 96, 29, 71, 98, 16, 11, 45, 32, 86, 95, 80, 95, 37]

Quick Sort: Recursive Divide-And-Conquer - O(n log n) Complexity

[11, 16, 26, 25, 28, 29, 32,32, 37, 45, 54, 71, 73, 80, 86, 95, 95, 95, 96, 98]

Time taken in nanoseconds: 8155500
Time taken in milliseconds: 10

>R

Returning to main menu...

Select your option in the menu below:
1: Initialize and populate an array of 20 random integers.
2: Perform a recursive binary search.
3: Perform a non-recursive binary search.
4: Sort the array
5: Quit
>5

Exiting...

Class BinarySearch:

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

class BinarySearch{
        
        // Non recursive binary search
        public int nonRecursiveBinarySearch(int arr[],int target)
        {
                int low=0,high=arr.length-1;
                while(low<=high)
                {
                        remainingElements(arr,low,high);
                        int mid=(low+high)/2;
                        if(arr[mid]==target)
                        {
                                System.out.println("Number "+target +" is found at index "+mid+" :Non recursive binary search");
                                return mid;
                        }
                        else if(arr[mid]<target)
                                low=mid+1;
                        else
                                high=mid-1;
                }
                System.out.println("Number "+target+" was not found   :Non recursive binary search");
                return -1;
        }
        // recursive binarySearch
        public int recursiveBinarySearch(int arr[],int first,int last,int target)
        {
                if(first<=last)
                {
                        remainingElements(arr,first,last);
                        int mid=(first+last)/2;
                        if(arr[mid]==target)
                        {
                                System.out.println("Number "+target +" is found at index "+mid+"  : recursive binary search");
                                return mid;
                        }
                        else if(arr[mid]<target)
                                return recursiveBinarySearch(arr,mid+1,last,target);
                        else
                                return recursiveBinarySearch(arr,first,mid-1,target);
                }
                // if not found
                System.out.println("Number "+target +" is not found : recursive binary search");
                return -1;
                
        }
        
        // display method will the array content between two index
        public void remainingElements(int arr[],int l,int r)
        {
                for(int i=l;i<=r;i++)
                        System.out.print(arr[i]+" ");
                System.out.println();
        }
        
        int[] generateRandomInts()
        {
                int arr[]=new int[20];
                Random rand=new Random();
                for(int i=0;i<20;i++)
                        arr[i]=rand.nextInt(89)+11; // generate between 11 to 99
                // sort the array
                Arrays.sort(arr);
                return arr;
        }
        
        public void calculateTime(int arr[],int target)
        {
                // for recusive 
                long start=System.nanoTime();
                recursiveBinarySearch(arr,0,arr.length-1,target);
                long time=System.nanoTime()-start;
                System.out.println("Recursive method will take "+time+"ns");
                
            start=System.currentTimeMillis();
                recursiveBinarySearch(arr,0,arr.length-1,target);
                time=System.currentTimeMillis()-start;
                System.out.println("Recursive method will take "+time+"ms");
                
                // for non  recusive 
                          start=System.nanoTime();
                                nonRecursiveBinarySearch(arr,target);
                                 time=System.nanoTime()-start;
                                System.out.println("Non Recursive method will take "+time+"ns");
                                
                            start=System.currentTimeMillis();
                                nonRecursiveBinarySearch(arr,target);
                                time=System.currentTimeMillis()-start;
                                System.out.println("Non Recursive method will take "+time+"ms");                                            
                
        }             
}

Test Class(main method):
public class Lab3binarysearchTest {
        
        public static void main(String[] args) {
                
       Scanner sc=new Scanner(System.in);
       BinarySearch bs=new BinarySearch();
       int arr[] = null;
       while(true)
       {
           System.out.println("Select your option int the menu below:\n"
                        + "1.Initialize and populate an array of 20 random integers\n"
                        + "2.Perform a recursive binary search\n"
                        + "3.Perfrom a non-recursive binary search\n"
                        + "4.Exit");
           int choice=sc.nextInt();
           if(choice==1)
           {
                   arr=bs.generateRandomInts();
                   System.out.println("Array of randomly generated integers:");
                   bs.remainingElements(arr, 0, arr.length-1);
                   
           }
           else if(choice==2)
           {
                   System.out.print("Please enter an integer value to search: ");
                int target=sc.nextInt();
                bs.recursiveBinarySearch(arr, 0, arr.length-1, target);
           }
           else if(choice==3)
           {
                   System.out.print("Please enter an integer value to search: ");
               int target=sc.nextInt();
               bs.nonRecursiveBinarySearch(arr, target);
           }
           else if(choice==4)
                   System.exit(0);
           else
                   System.out.println("Enter a valid choice");      
       }           
    }
}

Answer 1

ANSWER:

• I have provided the properly commented code in both text and image format so you can easily copy the code as well as check for correct indentation.
• I have provided the output image of the code so you can easily cross-check for the correct output of the code.
• Have a nice and healthy day!!

CODE TEXT

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class Main {
  
public static void menu()
{
System.out.println("Select your option in the menu\n"
+ "1.Initialize and populate an array of 20 random integers.\n"
+ "2.Perform a non -recursive binary Search\n"
+ "3.Perform Recursive binary search\n"
+ "4.Sorting\n"
+ "5.Exit");
  
}
public static void bubbleSort(int[] a) {
boolean sorted = false;
int temp;
while(!sorted) {
sorted = true;
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i+1]) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
sorted = false;
}
}
}
}

public static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int min = array[i];
int minId = i;
for (int j = i+1; j < array.length; j++) {
if (array[j] < min) {
min = array[j];
minId = j;
}
}
// swapping
int temp = array[i];
array[i] = min;
array[minId] = temp;
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int current = array[i];
int j = i - 1;
while(j >= 0 && current < array[j]) {
array[j+1] = array[j];
j--;
}
array[j+1] = current;
}
}

public static void mergeSort(int[] array, int left, int right) {
if (right <= left) return;
int mid = (left+right)/2;
mergeSort(array, left, mid);
mergeSort(array, mid+1, right);
merge(array, left, mid, right);
}
public static void merge(int[] array, int left, int mid, int right) {
// calculating lengths
int lengthLeft = mid - left + 1;
int lengthRight = right - mid;

// creating temporary subarrays
int leftArray[] = new int [lengthLeft];
int rightArray[] = new int [lengthRight];

// copying our sorted subarrays into temporaries
for (int i = 0; i < lengthLeft; i++)
leftArray[i] = array[left+i];
for (int i = 0; i < lengthRight; i++)
rightArray[i] = array[mid+i+1];

// iterators containing current index of temp subarrays
int leftIndex = 0;
int rightIndex = 0;

// copying from leftArray and rightArray back into array
for (int i = left; i < right + 1; i++) {
// if there are still uncopied elements in R and L, copy minimum of the two
if (leftIndex < lengthLeft && rightIndex < lengthRight) {
if (leftArray[leftIndex] < rightArray[rightIndex]) {
array[i] = leftArray[leftIndex];
leftIndex++;
}
else {
array[i] = rightArray[rightIndex];
rightIndex++;
}
}
// if all the elements have been copied from rightArray, copy the rest of leftArray
else if (leftIndex < lengthLeft) {
array[i] = leftArray[leftIndex];
leftIndex++;
}
// if all the elements have been copied from leftArray, copy the rest of rightArray
else if (rightIndex < lengthRight) {
array[i] = rightArray[rightIndex];
rightIndex++;
}
}
}
static int partition(int[] array, int begin, int end) {
int pivot = end;

int counter = begin;
for (int i = begin; i < end; i++) {
if (array[i] < array[pivot]) {
int temp = array[counter];
array[counter] = array[i];
array[i] = temp;
counter++;
}
}
int temp = array[pivot];
array[pivot] = array[counter];
array[counter] = temp;

return counter;
}

public static int recursiveBinarySearch(int arr[],int first,int last,int num)
{
if(first<=last)
{
remainingElements(arr,first,last);
int mid=(first+last)/2; // find the middle point of the array
if(arr[mid]==num) // if it is found at middle return mid as index
return mid;
if(arr[mid]<num) // if value at mid is less than numthen number num lies on the other side
return recursiveBinarySearch(arr,mid+1,last,num);
return recursiveBinarySearch(arr,first,mid-1,num);
}
return -1;
}

public static int nonRecursiveBinarySearch(int arr[],int num)
{
int first=0,last=arr.length-1;
while(first<=last)
{
remainingElements(arr,first,last);
int mid=(first+last)/2;
if(arr[mid]==num)
return mid;
if(arr[mid]<num)
first=mid+1;
else
last=mid-1;
}
return -1;
}
public static void remainingElements(int arr[],int l,int r)
{
for(int i=l;i<=r;i++)
{
System.out.print(arr[i]+" ");

}
System.out.println();
}

// Generate RandomInts
public static int[] generateRandomInts(int[] arr)
{

arr=new int[20];
Random rand=new Random();
for(int i=0;i<20;i++)
{
arr[i]=rand.nextInt(89)+11; // to generate between 10 and 100 excluding both

}

return arr;
}
public void timeExecution(int arr[],int num)
{
long start=System.nanoTime();
this.recursiveBinarySearch(arr, 0, arr.length-1, num);
long time=System.nanoTime()-start;
System.out.println("Time taken to search "+num+" using recursive search it is taking: "+time);

start=System.nanoTime();
this.nonRecursiveBinarySearch(arr, num);
time=System.nanoTime()-start;
System.out.println("Time taken to search "+num+" using non recursive search it is taking: "+time);
}
public static void quickSort(int[] array, int begin, int end) {
if (end <= begin) return;
int pivot = partition(array, begin, end);
quickSort(array, begin, pivot-1);
quickSort(array, pivot+1, end);
}
public static void main(String[] args) {
int[] arr ={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
Scanner sc=new Scanner(System.in);
// Binarysearch bin=new Binarysearch();
while(true)
{   
menu();
int choice=sc.nextInt();
if(choice==1)
{System.out.println("Array of randomly generated\n");
arr = generateRandomInts(arr);
int n=arr.length;
Arrays.sort(arr);
remainingElements(arr,0, n -1);
}
else if(choice==2)
{
  
System.out.println("Please enter an integer value to enter\n");
int num=sc.nextInt();
int index=nonRecursiveBinarySearch(arr, num);
if(index!=-1)
System.out.println("Number "+num+" is found at index "+index);
else {
System.out.println("Number "+num+" was not found!");

}
}
else if(choice==3)
{
  
System.out.println("Please enter an integer value to enter\n");
int num=sc.nextInt();
int index=recursiveBinarySearch(arr,0, arr.length-1, num);
if(index!=-1)
System.out.println("Number "+num+" is found at index "+index);
else {
System.out.println("Number "+num+" was not found!");
}   
}
else if(choice==4)
{
  
System.out.println("Select an algorithm to sort the data array\n");
System.out.println("B. Bubble Sort");
System.out.println("I. Insertion Sort");
System.out.println("S. Selection Sort");
System.out.println("M. Merge Sort");
System.out.println("Q. Quick Sort");
System.out.println("X. Return to Main Menu");
Scanner sd=new Scanner(System.in);
int n = arr.length;
char num=sd.next().charAt(0);
long start=System.nanoTime();
switch (num) {
case 'B': bubbleSort(arr);
break;
case 'I': insertionSort(arr);
break;
case 'S': selectionSort(arr);
break;
case 'M': mergeSort(arr, 0, n-1);
break;
case 'Q': quickSort(arr, 0, n-1);
break;
  
default:
break;
}
long time=System.nanoTime()-start;
remainingElements(arr,0, n -1);
  
switch (num) {
case 'B': System.out.println("Bubble Sort: Simple Sorting Algorithm - O(n^2) Complexity");
break;
case 'I': System.out.println("Insertion Sort: Simple Sorting Algorithm - O(n^2) Complexity");
break;
case 'S': System.out.println("Selection Sort: Simple Sorting Algorithm - O(n^2) Complexity");
break;
case 'M': System.out.println("Merge Sort: Recursive Divide-and-Conquer Algorithm - O( n log(n)) Complexity");
break;
case 'Q': System.out.println("Quick Sort: Recursive Divide-and-Conquer Algorithm - O( n log(n)) Complexity");
break;
  
default:
break;
}
System.out.println("Time taken in nanonseconds: "+time);
System.out.println("Time taken in milliseconds: "+time/1000000);

}
else
{
  
System.out.println("Exiting\n");
System.exit(0);
}
  
}
  
}

}

CODE IMAGES

OUTPUT IMAGE

Thanks and kindly upvote it will really help me . if you have any further queries kindly comment i will be happy to help.