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.
for(i = 0; i < n; i++) for(j = 1; j <= n; j = 2*j) System.out.println("Hello");
for(i = 1; i <= n; i = 3*i) for(j = 1; j <= n; j = 2*j) System.out.println("Hello");
for(i = 1; i <= n; i = 3*i) for(j = i; j < i+10; j = j+1) System.out.println("Hello");