ups and downs ..WHAT WAS MY MISTAKE

general
1

#include
using namespace std;
void merge(long long int *A,int p,int q,int r)
{

int n1,n2,i,j,L[1000],R[1000];
n1=q-p+1;
n2=r-q;
for(i=1;i<=n1;++i)
{
	L[i]=A[p+i-1];
}
for(i=1;i<=n2;++i)
{

	R[i]=A[q+i];
}
L[n1+1]=100006;
R[n2+1]=100006;
i=1;
j=1;
for(int k=p;k<=r;++k)
{
	if(L[i]<=R[j])
	{
		A[k]=L[i];
		++i;
	}
	else
	{
		A[k]=R[j];
		++j;
	}
}

}

void mergesort(long long int *A,int p,int r)
{
int q;
if(p<r)
{

	q=(p+r)/2;
	mergesort(A,p,q);
	mergesort(A,q+1,r);
	merge(A,p,q,r);
}

}
int main()
{
long long int array[100006],t,n,i,j;
cin>>t;
while(t–)
{
cin>>n;
for( i=1;i<=n;++i)
{
cin>>array[i];
}
mergesort(array,1,n);
for(i=1,j=n;i<=j;++i,–j)
{
if(i==j)
{
cout<<array[i];
}
else
{

			cout<<array[i]<<" "<<array[j]<<" ";
		}
	}
	cout<<"\n";
}
return 0;

}

2

First of all your code is (with possible error marked as comment) :

#include<iostream>

using namespace std;

void merge(long long int *A,int p,int q,int r)
{

        int n1,n2,i,j,L[1000],R[1000];//here is error

        n1=q-p+1;
        n2=r-q;

        for(i=1;i<=n1;++i)
           L[i]=A[p+i-1];

        for(i=1;i<=n2;++i)
           R[i]=A[q+i];

        L[n1+1]=100006;
        R[n2+1]=100006;
        
        i=1;
        j=1;

        for(int k=p;k<=r;++k) //here is error
        {
            if(L[i]<=R[j])
            {
                A[k]=L[i];
                ++i;
            }
            else
            {
                A[k]=R[j];
                ++j;
            }
        }

}

void mergesort(long long int *A,int p,int r)
{
    int q;
    
    if(p<r)
    {
            q=(p+r)/2;
            mergesort(A,p,q);
            mergesort(A,q+1,r);
            merge(A,p,q,r);
    }

}

int main()
{
    long long int array[100006],t,n,i,j;
    cin>>t;

    while(t--)
    {
        cin>>n;

        for(i=1;i<=n;++i)
             cin>>array[i];

        mergesort(array,1,n);

        for(i=1,j=n;i<=j;++i,--j)
        {
             if(i==j)
               cout<<array[i];
             else
               cout<<array[i]<<" "<<array[j]<<" ";
        }

        cout<<"\n";
    }

    return 0;

}

Everything is right in the code except your merge function. I replaced your merge sort with mine code and everything worked fine. It was Success full submission. In the merge function POSSIBLE ERRORS can be :

1.The limits of R[] and L[] are small as N can be of size 100000.
2.Now when you finally place elements of L[] and R[] back in A[] , the code is wrong.
Here’s why ?

suppose L= {1,2,3,4} and R={6,7,8,9} , then first of all elements of L will go in A but then as 4 is smaller than all R[] element i will keep on increasing and will move outside bounds of size of L.

3.The algorithm you choose to solve the problem is fine but it will takes about 5s to solve.You can reduce it to 1.5s using fast input or follow tutorial to get even more better algorithm to solve the problem.

  1. No Need of Long long int. int is sufficient.
1 Like
3

@chaseme when ever you want to sort, use qsort function easy to sort. In your code sorting is wrong.

1 Like
4

thanks…got ac