Q. Merge Sort

ALGORITHM:-

1.  break  array  into  arr[low..mid]  and  arr[mid+1..high]  until  there  is  1  element  left
2.  merge  these  both  arrays

#include<stdio.h>

void merge(int* arr,int low,int mid,int high)
{
    int b[1000];int i_b=low;
        int i=low,j=mid+1;

while(1)
{
   {
        if(i>mid)
        {
                for(int k=j;k<=high;k++)
                b[i_b++]=arr[k];
             break;
        }
     
        if(j>high)
        {
                for(int k=i;k<=mid;k++)
                b[i_b++]=arr[k];
           break;  
        }
 
   }
     
        if(arr[i]>=arr[j])
        {
        b[i_b++]=arr[j];j++;  
        }
        else
        {
        b[i_b++]=arr[i];i++;
        }    
}
for(int k=low;k<=high;k++)
arr[k]=b[k];
}



void mergeSort(int* arr,int low,int high)
{
if(low==high)
return;
int mid=(low+high) /2;
mergeSort(arr,low,mid);
mergeSort(arr,mid+1,high);
merge(arr,low,mid,high);
}


int main()
{
        int arr[10]={2,3,1,7,4,8,5,6,10,9};
        //int arr[10]={10,9,8,7,6,5,4,3,2,1};
        mergeSort(arr,0,9);
        for(int k=0;k<10;k++)
        printf("%d\t",arr[k]);
        return 0;
}

Q. Minimum Number of Jumps to reach out of Array starting from first element

Here  at  position  a[i]  we  can  jump  from  a[i]  to  a[i+a[i]]  positions

INPUT:  {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};

OUTPUT:  2  i.e  1->3->9

METHOD  1  DP

DP  can  be  used  as  reaching  i  th  index  we  require

 a[i]=a[j]+j  where  j <= i

so  dp[i]=dp[j]+1;  where  i th  index  stores number  of  jumps  to  reach  a[i]

#include<stdio.h>
int max(int* dp,int n)
{
int max=0;
for(int i=0;i<n;i++)
if(dp[i]>max)
max=dp[i];
return max;
}
int main()
{
int n=11;
int arr[11]={1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
int dp[11]={0,0,0,0,0,0,0,0,0,0,0};
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(i==j+arr[j])
{dp[i]=dp[j]+1;break;} }
}
if(dp[n-1]!=0)
printf("%d",dp[n-1]);
else
{
printf("%d",max(dp,n)); }
}

Time  =O(n^2)
Space=O(n)  for  dp  array

METHOD  2  GREEDY

Here  we  can  also  use  greedy  approach  as  we  can  see  we  may  choose  max{j+a[j]}  as  our  next  move  i.e  we  can  reach  destination  as  easy  as  possible

#include<stdio.h>
int max(int* arr,int low, int high)
{
printf("%d   %d\n",low,high);
int max=0;
for(int i=low;i<=high;i++)
if(i+arr[i]>max)
max=arr[i]+i;
return max;
}
int main()
{
int n=11;
int arr[11]={1, 1, 2, 5, 1, 2, 2, 1, 1, 8, 9};
int jump=0;
for(int i=0;i<n;)
{
//printf("%d\t",i);
i=max(arr,i+1,i+arr[i]);
jump++;
if(i>11)
break;
}
printf("%d",jump+1);
}

Time=  O(n)

Please  suggest  any  updates.........