Consider the algorithm DoSomething below a) Can the runtime of DoSomething be im
ID: 3599588 • Letter: C
Question
Consider the algorithm DoSomething below
a) Can the runtime of DoSomething be improved easily? Explain how (i.e. re-write another solution using Java that does exactly what DoSomething is doing more efficiently)?
b) Can the space complexity of DoSomething be improved? Explain how?
Explanation / Answer
Actual Program without any runtime or space improved in java:-
(This actually does sorting in ascending order)
import java.util.*;
public class Prog1{
public int[] DoSomething(int[] A,int n){
int[] Zom=new int[n];
int[] M=new int[n];
Arrays.fill(Zom,0);
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(A[i] <= A[j]){
Zom[j]=Zom[j]+1;
}
else{
Zom[i]=Zom[i]+1;
}
}
}
for(int i=0;i<n;i++){
M[Zom[i]]=A[i];
}
return M;
}
public static void main(String []args){
Prog1 obj=new Prog1();
int[] arr=new int[5];
arr[0]=50;
arr[1]=4;
arr[2]=33;
arr[3]=2;
arr[4]=44;
int[] arr_ret=new int[5];
arr_ret=obj.DoSomething(arr,5);
for(int i=0;i<5;i++){
System.out.println(arr_ret[i]);
}
}
}
Question 2)
Space Improved:-
Explanation :- In previous given question,there are 3 arrays extra used instead of the given array as arguement,here we are just using the arguement array and one temporary variable.So ,we are saving memory of 3 extra arrays
import java.util.*;
public class Prog1{
public int[] DoSomething(int[] A,int n){
int temp;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (A[i] > A[j])
{
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
return A;
}
public static void main(String []args){
Prog1 obj=new Prog1();
int[] arr=new int[5];
arr[0]=50;
arr[1]=4;
arr[2]=33;
arr[3]=2;
arr[4]=44;
int[] arr_ret=new int[5];
arr_ret=obj.DoSomething(arr,5);
for(int i=0;i<5;i++){
System.out.println(arr_ret[i]);
}
}
}
Question 1)
Runtime improved:-
Explanation:- here not only we are saving space but time also,space first we are not using the extra 3 arrays but also not using extra loops to fill up zeros or for sorting. here,we are using insertion sort method for sorting which is faster than bubble where side by side comparison takes place causing n*n loops instead we are using insertion where n log(n) times loop occurs
import java.util.*;
public class Prog1{
public int[] DoSomething(int[] A,int n){
int temp;
for (int i=1; i<n; ++i)
{
int element = A[i];
int j = i-1;
while (j>=0 && A[j] > element)
{
A[j+1] = A[j];
j = j-1;
}
A[j+1] = element;
}
return A;
}
public static void main(String []args){
Prog1 obj=new Prog1();
int[] arr=new int[5];
arr[0]=50;
arr[1]=4;
arr[2]=33;
arr[3]=2;
arr[4]=44;
int[] arr_ret=new int[5];
arr_ret=obj.DoSomething(arr,5);
for(int i=0;i<5;i++){
System.out.println(arr_ret[i]);
}
}
}