Consider the algorithm DoSomething below a) Can the runtime of DoSomething be im

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?

Algorithm DoSomething (A, n) Input: Array A of integer containing n elements Output: Array M of integer containing n elements 1. for i-0 to n-1 do 2. Zomli]-0 3. end for 4. for i-0 to n-2 do 5. forj-it1 ton-1 do 6. ifAliJKAi] then 7. 8. else .end if 11. end for 12. end for 13. for i-0 to n-1 do 14. MZom [i]]=A[i] 15. end for 16. Return M 10.

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]);
        }
     }
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.