In the Course Files section there is a demonstration of a technique for measurin
ID: 3576604 • 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.*;
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
class BST
{
// Root of Binary Tree
Node root;
int counter;
public BST()
{
root = null;
}
// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(Node node)
{
if (node == null)
return;
/* first recur on left child */
printInorder(node.left);
/* then print the data of node */
counter +=1;
if(counter < 31) System.out.print(node.key + " ");;
/* now recur on right child */
printInorder(node.right);
}
}
public class Sort_compare{
public static void bubbleSort(List<Integer> arr) {
int n = arr.size();
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr.get(j-1) > arr.get(j)){
//swap elements
temp = arr.get(j-1);
arr.set(j-1, arr.get(j));
arr.set(j, temp);
}
}
}
}
public static void print_first(List<Integer> arr){
for (int i = 0; i < 25; i++ ) {
System.out.print( arr.get(i) + " ");
}
System.out.println(" ");
}
public static void main(String[] args) {
int N = 100;
BST bst = new BST();
long start = System.currentTimeMillis();
List<Integer> arr = new ArrayList<Integer>();
for (int i = 0 ; i < N; i++ ) {
int range = 10*N;
Random r = new Random();
int number = (int)(r.nextDouble()*range);
bst.insert(number);
arr.add(number);
}
long time = System.currentTimeMillis() - start;
System.out.println("BST for "+ N + " numbers take " + time + " ms ");
bst.printInorder(bst.root);
System.out.println(" ");
start = System.currentTimeMillis();
bubbleSort(arr);
time = System.currentTimeMillis() - start;
System.out.println("bubble sort for "+ N + " numbers take " + time + " ms ");
print_first(arr);
System.out.println("******************************************** ");
N = 1000;
bst = new BST();
start = System.currentTimeMillis();
arr = new ArrayList<Integer>();
for (int i = 0 ; i < N; i++ ) {
int range = 10*N;
Random r = new Random();
int number = (int)(r.nextDouble()*range);
bst.insert(number);
arr.add(number);
}
time = System.currentTimeMillis() - start;
System.out.println("BST for "+ N + " numbers take " + time + " ms ");
bst.printInorder(bst.root);
System.out.println(" ");
start = System.currentTimeMillis();
bubbleSort(arr);
time = System.currentTimeMillis() - start;
System.out.println("bubble sort for "+ N + " numbers take " + time + " ms ");
print_first(arr);
System.out.println("******************************************** ");
N = 10000;
bst = new BST();
start = System.currentTimeMillis();
arr = new ArrayList<Integer>();
for (int i = 0 ; i < N; i++ ) {
int range = 10*N;
Random r = new Random();
int number = (int)(r.nextDouble()*range);
bst.insert(number);
arr.add(number);
}
time = System.currentTimeMillis() - start;
System.out.println("BST for "+ N + " numbers take " + time + " ms ");
bst.printInorder(bst.root);
System.out.println(" ");
start = System.currentTimeMillis();
bubbleSort(arr);
time = System.currentTimeMillis() - start;
System.out.println("bubble sort for "+ N + " numbers take " + time + " ms ");
print_first(arr);
System.out.println("******************************************** ");
N = 100000;
bst = new BST();
start = System.currentTimeMillis();
arr = new ArrayList<Integer>();
for (int i = 0 ; i < N; i++ ) {
int range = 10*N;
Random r = new Random();
int number = (int)(r.nextDouble()*range);
bst.insert(number);
arr.add(number);
}
time = System.currentTimeMillis() - start;
System.out.println("BST for "+ N + " numbers take " + time + " ms ");
bst.printInorder(bst.root);
System.out.println(" ");
start = System.currentTimeMillis();
bubbleSort(arr);
time = System.currentTimeMillis() - start;
System.out.println("bubble sort for "+ N + " numbers take " + time + " ms ");
print_first(arr);
System.out.println("******************************************** ");
N = 1000000;
bst = new BST();
start = System.currentTimeMillis();
arr = new ArrayList<Integer>();
for (int i = 0 ; i < N; i++ ) {
int range = 10*N;
Random r = new Random();
int number = (int)(r.nextDouble()*range);
bst.insert(number);
arr.add(number);
}
time = System.currentTimeMillis() - start;
System.out.println("BST for "+ N + " numbers take " + time + " ms ");
bst.printInorder(bst.root);
System.out.println(" ");
start = System.currentTimeMillis();
bubbleSort(arr);
time = System.currentTimeMillis() - start;
System.out.println("bubble sort for "+ N + " numbers take " + time + " ms ");
print_first(arr);
}
}
OUTPUT
BST for 100 numbers take 1 ms
11 12 34 35 40 42 44 46 53 72 84 87 108 117 128 142 149 151 154 158 179 182 185 189 190 194 205 210 217 237
bubble sort for 100 numbers take 4 ms
11 12 34 35 40 42 44 46 53 72 84 87 108 117 128 142 149 151 154 158 179 182 185 189 190
********************************************
BST for 1000 numbers take 3 ms
0 31 36 49 56 59 62 65 77 84 87 89 106 114 117 118 124 141 150 160 171 183 194 199 206 211 213 235 236 257
bubble sort for 1000 numbers take 39 ms
0 31 36 49 49 56 59 62 65 77 84 87 89 106 114 117 118 124 141 150 160 171 183 194 199
nilmadhab@nilmadhab-Inspiron-3542:~/Desktop/chegg/answers/java$ javac Sort_compare.java
nilmadhab@nilmadhab-Inspiron-3542:~/Desktop/chegg/answers/java$ java Sort_compare
BST for 100 numbers take 1 ms
32 33 34 52 65 73 81 99 109 114 115 126 132 140 142 157 160 164 183 192 218 220 254 283 292 295 300 301 308 324
bubble sort for 100 numbers take 2 ms
32 33 34 52 65 73 81 99 109 114 115 126 132 140 142 157 157 160 164 183 192 218 218 220 220
********************************************
BST for 1000 numbers take 1 ms
0 1 14 15 17 46 47 60 83 84 86 96 101 102 117 126 127 135 148 156 174 199 213 237 246 248 255 261 281 287
bubble sort for 1000 numbers take 28 ms
0 1 14 15 17 46 47 60 83 84 86 96 101 102 117 126 127 135 135 135 148 156 174 199 213
********************************************
BST for 10000 numbers take 7 ms
1 2 4 5 15 30 32 41 47 60 71 73 90 94 119 126 152 162 165 171 177 189 203 205 214 216 229 247 266 271
bubble sort for 10000 numbers take 561 ms
1 2 4 5 15 30 32 41 47 60 71 73 90 94 119 126 152 162 165 171 177 189 203 205 214
********************************************
BST for 100000 numbers take 61 ms
3 6 12 15 22 32 37 49 56 60 61 69 71 72 73 75 83 99 107 127 130 150 154 177 203 205 241 261 272 284