In the Course Files section there is a demonstration of a technique for measurin
ID: 3576567 • 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
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Stack;
class Node {
int data;
Node left, right;
Node(int d) {
data = d;
left = right = null;
}
}
class Index {
int index = 0;
}
class BinaryTree {
Index index = new Index();
Node constructTreeUtil(int pre[], Index preIndex,
int low, int high, int size) {
// Base case
if (preIndex.index >= size || low > high) {
return null;
}
Node root = new Node(pre[preIndex.index]);
preIndex.index = preIndex.index + 1;
if (low == high) {
return root;
}
int i;
for (i = low; i <= high; ++i) {
if (pre[i] > root.data) {
break;
}
}
root.left = constructTreeUtil(pre, preIndex, preIndex.index, i - 1, size);
root.right = constructTreeUtil(pre, preIndex, i, high, size);
return root;
}
Node constructTree(int pre[], int size) {
return constructTreeUtil(pre, index, 0, size - 1, size);
}
public void printInorder(Node root) {
if (root == null) {
return;
}
Stack<Node> s = new Stack<>();
List<Integer> list1 = new ArrayList<>();
Node currentNode = root;
while (!s.empty() || currentNode != null) {
if (currentNode != null) {
s.push(currentNode);
currentNode = currentNode.left;
} else {
Node n = s.pop();
//System.out.printf("%d ",n.data);
list1.add(n.data);
currentNode = n.right;
}
}
for (int i = 0; i < 30; i++) {
System.out.print(list1.get(i) + " ");
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
Random random = new Random();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
int j = getRandomInteger(1, 1000);
list.add(j);
}
System.out.println("Bubble Sort");
System.out.println();
long lStartTime = System.nanoTime();
for (int i = list.size() - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (list.get(j) > list.get(j + 1)) {
int temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}
}
}
long lEndTime = System.nanoTime();
long output = lEndTime - lStartTime;
System.out.println("Total Time taken for Buble sort in milliseconds: are " + output / 1000000);
for (int i = 0; i < 25; i++) {
System.out.print(list.get(i) + " ");
}
list.clear();
System.out.println();
for (int i = 0; i < 100; i++) {
int j = getRandomInteger(1, 1000);
list.add(j);
}
Collections.sort(list);
int pre[] = new int[list.size()];
for (int j = 0; j < list.size(); j++) {
pre[j] = list.get(j);
}
int size = pre.length;
Node root = tree.constructTree(pre, size);
System.out.println("Inorder traversal of the constructed tree is ");
long lStartTime1 = System.nanoTime();
tree.printInorder(root);
long lEndTime1 = System.nanoTime();
long output1 = lEndTime1 - lStartTime1;
System.out.println();
System.out.println("Total Time taken for Inorder traversal in milliseconds: are " + output1 / 1000000);
}
public static int getRandomInteger(int maximum, int minimum) {
return ((int) (Math.random() * (maximum - minimum))) + minimum;
}
}