Project 2: Arrays, Sorting algorithms, Determining execution time

Code a java class named Project2 with a main routine containing a loop that executes the following steps with values of N = 1000, 10000, 100000, 1000000, 10000000 and 100000000 (if possible):

   determine the value of N
   repeat 5 times
        create an array of N random integers
        sort the array using bubblesort and note the time required to complete this sort
   repeat 5 times
        create an array of N random integers
        sort the array using Arrays.sort(...) and note the time required to complete this sort
   for this array size
        calculate the average and worst times for bubblesort
        calculate the average and worst times for Arrays.sort()
   

The signature of your bubblesort method should be

	public static void bubblesort(int [] array)
	

Call the System.nanoTime() method before and after the calls to bubblesort and Arrays.sort() and compute the amount of time required to do the sorting. You can do this by placing the statement

	long startingTime=System.nanoTime();
	

immediately before the call to the sorting method and the statement

	long duration = System.nanoTime() - startingTime;
	

immediately after the call.

You can copy the bubblesort and swap methods from your textbook (pages 85-86) and adapt them to work with an integer array. For simplicity, define both of these as static methods in your Project2 class so they can be called from main() or elsewhere without having to create any new instances of objects.

Your main routine should display the time required for the sorts on your console. Run your code to make sure it works. In fact, you should run it a couple of times and watch for the "worst case" sorting time as well as the "average" sorting time. Different random arrays could require significantly different sorting times. Recall that you can create an array of random integers by creating an instance of the Random class (from the java.util package) and calling its nextInt() method repeatedly to get a random sequence of integers.

Arrange your final output in a table like the following one and display the table contents on the console.

Array Size	bubblesort time	Arrays.sort time
1,000
10,000
100,000
1,000,000
10,000,000
100,000,000

You are expecting to see, eventually … when N is large enough, O(N²) growth in the bubblesort column. If the size of the array increases by a factor of 10, the sorting time is expected to increase by a factor of 100. It may even be worse than this if memory constraints start to cause some paging activity or other system turmoil. If the Arrays.sort method is a good one, we might expect to see O(N*log(N)) growth in that column. As the size of the array increases by a factor of 10, the Arrays.sort time would be expected to increase by a factor of 10*N*log(10*N)/(N*log(N)) = 10*N*(1+log(N))/(N*log(N)) = 10/log(N) + 10 which, for large values of N, might look almost like an increase by a factor of 10.

Use the nanoTime() method carefully, so that you are only measuring the time to do the actual sorting of the array. You don't want to include the time it takes to create the array or initialize it with random values. You also don't want to count any time spent displaying results so don't do any input or output while your nanoTime() counter is running.

All your code should be in one file named Project2.java. Attach your solution to an e-mail and send it to Joel Carver on or before midnight on Tuesday, October 13, 2009.