In the Course Files section there is a demonstration of a technique for measurin
ID: 3576544 • Letter: I
Question
In the Course Files section there is a demonstration of a technique for measuring the time it takes to run a program on a collection of data. Use that technique for the following experiment.
Create a Java program that carries out the following experiment using long integers.
1. Start with N = 100 .
2. Build an array list of N integer values which are randomly generated integers between 1 and 10N.
3.Sort the array list using Bubble Sort. (Determine the time it takes to create the sorted array.)
4. Build a binary search tree of N integer values which are randomly generated integers between 1 and 10N. (Determine the time it takes to create the tree.)
5. Display N and the times for the two constructions.
6. Display the first 25 elements of the array list. (They will necessarily be in sorted order.)
7. Display the first 31 elements of the binary search tree in in-order. (The will necessarily be in sorted order.)
Repeat this experiment for N = 10^3, 10^4, ... until you run out of space or time.
Prepare a report that gives your timing results.
Hand-in your program, including the source code, and your report.
Explanation / Answer
Answer
Java code covering 1, 2 , 3, 5 and 6 of the question is as below:
import java.util.Scanner;
import java.util.Random;
public class BS_BST {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = 100;
int i = 0;
int j=0;
long temp = 0;
System.out.println("Enter the size of the array:: ");
n = input.nextInt();
long arr[] = new long[n];
/*Filling the array with random numbers between 1 to 10N*/
for(i = 0; i<n; i++)
{
Random rand = new Random();
arr[i] = rand.nextInt(((10*n) - 1) + 1) + 1;
}
/*Sorting the array in ascending order using bubble sort*/
for(i = 0; i<n; i++)
{
for(j = 1; j<(n-i); j++)
{
if(arr[j-1]>arr[j])
{
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println("The value of N is "+n);
System.out.println("The run time of Bubble sort in the worst case scenario is n^2");
System.out.println("The 1st 25 elements of the sorted array (if 25 elements present) are ::");
if(n>25)
j=25;
else
j = n;
for(i = 0; i<j; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}