public static void bubbleSort(int[] list) { int n = list.length; for(i = 0; i < n-1; i++) for(j = n-2; j >= i; j--) if(list[j] > list[j+1]) swap(list, j, j+1); }Version B is the modified version of Version A that stops sorting as soon as it detects that the array is sorted.
To perform the experiments, you should generate two types of arrays.
You are required to perform 4 sets of timing experiments, by running: (a) Version A of bubble sort on "almost sorted" input, (b) Version A of bubble sort on "almost unsorted" input, (c) Version B of bubble sort on "almost sorted" input, and (d) Version B of bubble sort on "almost unsorted" input. For each experiment, obtain the running time on arrays of size 1000, 2000, 3000, ..., 10000. You will therefore get 10 running times from each experiment. Plot these running times using your favorite plotting software (Excel, Mathematica, etc.) and connect these points with a smooth curve. You should have 4 plots. Write 3-4 sentences explaining what you see and whether your observations confirm your calculations from Homework 1.
Some more details. To slightly perturb the contents of an array, you are asked to randomly generate pairs of indices. To randomly generate an integer you can use the class Random defined in java.util. To learn more about this class see this page at java.sun.com. To time your functions use the function System.currentTimeMillis(). Here is an example of the bubble sort algorithm being timed.
Solution: Here are three programs that time bubbleSort and improvedBubbleSort: TimingBubbleSort1.java, TimingBubbleSort2.java, and TimingBubbleSort3.java. The first runs the two versions on bubble sort on almost sorted arrays, the second runs these on almost unsorted arrays, and the third runs these on almost sorted arrays obtained using a different kind of small perturbation. For timing plots and comments on these plots, see comments.pdf.
for(i = 0; i < n; i++) for(j = 1; j <= n; j = 2*j) System.out.println("Hello");Solution: The body of the outer loop execues n times. The body of the inner loop executes log_2 n times, independent of what the loop control variable i, of the outer loop is. Therefore, the running time of the code fragment is O(n log_2 n).
for(i = 1; i <= n; i = 3*i) for(j = 1; j <= n; j = 2*j) System.out.println("Hello");Solution: The body of the outer loop execues log_3 n times. The body of the inner loop executes log_2 n times, independent of what the loop control variable i, of the outer loop is. Therefore, the running time of the code fragment is O(log^2 n). Note that it is ok to skip writing the base of the logarithm, inside the Big Oh notation.
for(i = 1; i <= n; i = 3*i) for(j = i; j < i+10; j = j+1) System.out.println("Hello");
In addition to your answer, show your calculations also. However, your calculations need not be as detailed as for Homework 1, Problem 1.