Question

For this lab assignment you will need to write some code and create some graphs. You may use excel to create your graphs, or other language of your choice. Your data needs to demonstrate the experimental running time for Selection Sort (code in book), Merge Sort (code in book), and the Arrays.sort() method.

Here is a basic outline of how you need to code this assignment.

1) Create several arrays of size 100, 1000, 10000, 100000, 1000000, … (you need to choose max size appropriately).

2) Start the stop watch (class provided in book).

3) Sort the array

4) Stop the stop watch

5) Print (or write to a file) the size of the array and the time it took to sort.

You will follow the above outline for each sorting algorithm. You will need to plot size of array (x-axis) vs time (y-axis) on a log-log scale. (This can be done easily in excel). You should have all three sets of data on the same graph. (so use the same array sizes for all 3 tests). (On a log-log scale, all data should be a straight line, but the slope of a O(n2) algorithm will be higher than an O(n log n) algorithm). I have an example shown below of a graph of 3 functions on a log-log scale.

You also need to include plots on a standard scale. Create a single graph with all three sorting algorithms’ data on that single plot.

You may print your values to the screen and copy / paste into excel. Or you may create CSV files and open them directly with excel. (CSV file is simply a text file, with values separated by commas – CSV stands for Comma Separated Values).

To Turn In

Turn in your java code, your excel files (or whatever you used to create your visualization), and a PDF document with your chart, and a short report (1-2 pages) describing how you did this assignment, and the differences between the run times of the algorithms you tested. You can find the run times of all algorithms on the internet. Did your experiments line up with your expectations of run time?

Answer 1

import java.util.Random;
import java.util.Arrays;

public class JavaApplication5 {

  
public static void main(String[] args) {
// TODO code application logic here
long[][] starttime, endtime;
starttime =new long[6][3];
endtime = new long[6][3];
//System.out.println("Hi");
Random rd = new Random();
int[] arr1 = new int[10];
int[] arr2 = new int[100];
int[] arr3 = new int[1000];
int[] arr4 = new int[10000];
int[] arr5 = new int[100000];
int[] arr6 = new int[1000000];
/*int[] arr7 = new int[10000000];
int[] arr8 = new int[100000000];*/
int[] oldarr1 = new int[10];
int[] oldarr2 = new int[100];
int[] oldarr3 = new int[1000];
int[] oldarr4 = new int[10000];
int[] oldarr5 = new int[100000];
int[] oldarr6 = new int[1000000];
createArray(arr1);
createArray(arr2);
createArray(arr3);
createArray(arr4);
createArray(arr5);
createArray(arr6);
copyArray(arr1,oldarr1);
copyArray(arr2,oldarr2);
copyArray(arr3,oldarr3);
copyArray(arr4,oldarr4);
copyArray(arr5,oldarr5);
copyArray(arr6,oldarr6);
/*createArray(arr6);
createArray(arr7);
createArray(arr8);*/
  
int r=0, c=0;
  
starttime[r][c] = System.currentTimeMillis();
selectionSort(arr1);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr1,arr1);
starttime[r][c] = System.currentTimeMillis();
mergeSort(arr1,0,arr1.length-1);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr1,arr1);
starttime[r][c] = System.currentTimeMillis();
Arrays.sort(arr1);
endtime[r][c] = System.currentTimeMillis();
  
r++;
c=0;
starttime[r][c] = System.currentTimeMillis();
selectionSort(arr2);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr2,arr2);
starttime[r][c] = System.currentTimeMillis();
mergeSort(arr2,0,arr2.length-1);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr2,arr2);
starttime[r][c] = System.currentTimeMillis();
Arrays.sort(arr2);
endtime[r][c] = System.currentTimeMillis();

r++;
c=0;
starttime[r][c] = System.currentTimeMillis();
selectionSort(arr3);
endtime[r][c] = System.currentTimeMillis();
c++;

copyArray(oldarr3,arr3);
starttime[r][c] = System.currentTimeMillis();
mergeSort(arr3,0,arr3.length-1);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr3,arr3);
starttime[r][c] = System.currentTimeMillis();
Arrays.sort(arr3);
endtime[r][c] = System.currentTimeMillis();
  
r++;
c=0;
starttime[r][c] = System.currentTimeMillis();
selectionSort(arr4);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr4,arr4);
starttime[r][c] = System.currentTimeMillis();
mergeSort(arr4,0,arr4.length-1);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr4,arr4);
starttime[r][c] = System.currentTimeMillis();
Arrays.sort(arr4);
endtime[r][c] = System.currentTimeMillis();
  
r++;
c=0;
starttime[r][c] = System.currentTimeMillis();
selectionSort(arr5);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr5,arr5);
starttime[r][c] = System.currentTimeMillis();
mergeSort(arr5,0,arr5.length-1);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr5,arr5);
starttime[r][c] = System.currentTimeMillis();
Arrays.sort(arr5);
endtime[r][c] = System.currentTimeMillis();
  
r++;
c=0;
starttime[r][c] = System.currentTimeMillis();
selectionSort(arr6);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr6,arr6);
starttime[r][c] = System.currentTimeMillis();
mergeSort(arr6,0,arr6.length-1);
endtime[r][c] = System.currentTimeMillis();
c++;
  
copyArray(oldarr6,arr6);
starttime[r][c] = System.currentTimeMillis();
Arrays.sort(arr6);
endtime[r][c] = System.currentTimeMillis();
  
for(int i=0;i<6;i++) {
for(int j=0;j<3;j++)
System.out.print(endtime[i][j]-starttime[i][j] + " ");
System.out.println();
}
}
public static void selectionSort(int[] arr){
for (int i = 0; i < arr.length - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;//searching for lowest index
}
}
int smallerNumber = arr[index];   
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
public static void mergeSort(int a[], int beg, int end)
{
int mid;
if(beg<end)
{
mid = (beg+end)/2;
mergeSort(a,beg,mid);
mergeSort(a,mid+1,end);
merge(a,beg,mid,end);
}
}
public static void merge(int a[], int beg, int mid, int end)
{
int i=beg,j=mid+1,k,index = beg;
int[] temp = new int[100000];
while(i<=mid && j<=end)
{
if(a[i]<a[j])
{
temp[index] = a[i];
i = i+1;
}
else   
{
temp[index] = a[j];
j = j+1;   
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index] = a[j];
index++;
j++;
}
}
else   
{
while(i<=mid)
{
temp[index] = a[i];
index++;
i++;
}
}
k = beg;
while(k<index)
{
a[k]=temp[k];
k++;
}
}
public static void createArray(int[] arr) {
Random rd = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = rd.nextInt();
}
}
public static void copyArray(int[] source, int[] target) {
  
for (int i = 0; i < source.length; i++) {
target[i] = source[i];
}
}
public static void printArray(int[] arr) {
  
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}

This Java program produces the following output:

Copy this data into an excel sheet and plot the line graph.

Array Size	Selection Sort	Merge Sort	Arrays.Sort	log (Size)	log(Time)	log(Time)	log(Time)
10	0	0	0	1	0	0	0
100	0	31	0	2	0	0	0
1000	0	312	0	3	0	2.494155	0
10000	156	2952	16	4	2.193125	3.470116	1.20412
100000	15750	32701	16	5	4.197281	4.514561	1.20412

I declared 5 arrays of sizes 10, 100, 1000, 10000, 100000 and 100000. Using nextInt() method in Random package I populated the array elements. As I wanted to use the same set of arrays for all the three sort alfoerithms, I kept a copy of these arrays in another set of arrays. Everytime before calling the sorting algorithms I copied these backup arrays into my reglar set of arrays that are passed as input to sorting methods. I used System.currentTimeMillis() to log the time before and after calling the sorting methods. The difference between these two times give the elapsed time for that sorting method. I stored the elapsed time for all the sorting methods for the set of arrays into a 2d array and printed it as a table. I copied this table into excel and plotted the line graph.