Question

Do a theta analysis and count the number of computations it performed in each function/method of the following code:

import java.io.*;
import java.util.Scanner;

class sort
{
int a[];
int n;
long endTime ;
long totalTime;
long startTime;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public sort(int nn) // Constructor
{
a = new int[nn];
n = nn;
endTime= 0;
totalTime =0;
startTime =0;
}
public static void main(String args[]) throws IOException
{
System.out.print("\nEnter number of students: ");
int nn = Integer.parseInt(br.readLine());
sort call = new sort(nn);

// Read array from user
System.out.println("\nEnter " +nn +" student's ID numbers:");
call.readArray();

// Ask for choosing the sorting technique
System.out.println("Choose Sorting Technique :\n");
System.out.println("1 : Bubble Sort");
System.out.println("2 : Selection Sort");
System.out.println("3 : Insertion Sort");
System.out.println("4 : Quick Sort");
System.out.println("5 : Merge Sort");
System.out.print("\nYour Choice : ");
int choice = Integer.parseInt(br.readLine());
switch(choice)
{
case 1:
call.bubbleSort();
break;
case 2:
call.selectionSort();
break;
case 3:
call.insertionSort();
break;
case 4:
call.quickSort();
break;
case 5:
call.mergeSort();
break;
default :
System.out.println("\nInvalid Choice !");
System.exit(1);
break;
}
call.display(); // Print the sorted array
call.firstLastName();
}
public void readArray() throws IOException
{
for(int i=0;i<n;i++)
a[i] = Integer.parseInt(br.readLine());
}
public void bubbleSort()
{
int t;
startTime = System.currentTimeMillis();
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println(totalTime);

}
public void firstLastName() {
int n;
String temp;
Scanner s = new Scanner(System.in);
System.out.print("Enter number of names you want to enter:");
n = s.nextInt();
String names[] = new String[n];
Scanner s1 = new Scanner(System.in);
System.out.println("Enter all the names names:");
for(int i = 0; i < n; i++)
{
names[i] = s1.nextLine();
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (names[i].compareTo(names[j])>0)
{
temp = names[i];
names[i] = names[j];
names[j] = temp;
}
}
}
System.out.print("Names in Sorted Order: ");
for (int i = 0; i < n - 1; i++)
{
System.out.print(names[i] + ", ");
}
System.out.print(names[n - 1]);
System.out.println();

}
public void selectionSort()
{
startTime = System.currentTimeMillis();
int t, min;
for(int i=0;i<n-1;i++)
{
min = i;
for(int j=i+1;j<n;j++)
{
if(a[min]>a[j])
min = j;
}
if(min!=i)
{
t = a[min];
a[min] = a[i];
a[i] = t;
}
}
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println(totalTime);
}
public void insertionSort()
{
startTime = System.currentTimeMillis();
int t,j;
for(int i=1;i<n;i++)
{
j = i-1;
t = a[i];
while(t<a[j] && j>=0)
{
a[j+1] = a[j];
j--;
}
a[j+1] = t;
}
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println(totalTime);
}
public void quickSort()
{
startTime = System.currentTimeMillis();
int t;
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println(totalTime);
}
static void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;

/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];

/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];

/* Merge the temp arrays */

// Initial indexes of first and second subarrays
int i = 0, j = 0;

// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

public void mergeSort(int arr[], int l, int r) {
startTime = System.currentTimeMillis();
if (l < r)
{
// Find the middle point
int m = (l+r)/2;

// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr , m+1, r);

// Merge the sorted halves
merge(arr, l, m, r);
}
}
public void display()
{
System.out.println("\nSorted Array :");
for(int i=0;i<n;i++)
System.out.println(a[i]);
}

}

Answer 1