In the Course Files section there is a demonstration of a technique for measurin

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.Calendar; import java.util.Random; public class Sorting { public static void main(String args[]) { int[] bubbleSortArray = randomArray(1, 10000); Calendar c3=Calendar.getInstance(); System.out.println(c3.getTime()); bubbleSort(bubbleSortArray); Calendar c4=Calendar.getInstance(); System.out.println(c4.getTime()); System.out.println("bubble sort time taken in milliseconds : "+(c4.getTimeInMillis()-c3.getTimeInMillis())); System.out.println("First 25 elements sorted using bubble sort ara as follows...."); for (int i=0;i< 25;i++) { System.out.println(bubbleSortArray[i]); } } /** * Method to create the random array. * @param initialNumber * @param lastNumber * @return */ private static int[] randomArray(int initialNumber, int lastNumber) { int[] array = new int[100]; Random randomGenerator = new Random(); for (int idx = 0; idx < 100; ++idx) { int randomInt = randomGenerator.nextInt(lastNumber); array[idx] = randomInt; } return array; } /** * Method to sort the array using bubble sort. * @param arr array to be sorted. */ private static void bubbleSort(int[] arr) { int n = arr.length; int temp = 0; for (int i = 0; i arr[j]) { //swap elements temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; } } } } }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---