why is this code giving runtime error

general
1

#include
using namespace std;
int main()
{
int t,i,k,l;
int z[100000];
cin>>t;
for (i=0;i<=t-1;i++)
{cin>>z[i];
}
int temp;
for (l=0;l<=t-2;l++)
{ for (k=0;k<=t-2;k++)
if (z[k+1]<z[k])
{temp=z[k];
z[k]=z[k+1];
z[k+1]= temp;
}
else
continue;
}
for (l=0;l<=t-1;l++)
{cout<<z[l]<<endl;
}
}

2

It works for me. Where are you the facing problem? Or could you give the sample inputs where you are getting the runtime error?

3

Whenever you ask a doubt, always provide the problem link.

I had to go through your profile to get to the problem page. Anyway, following is the problem.

https://www.codechef.com/problems/TSORT

The reason that you are getting a Runtime Error (RE) is that you have declared the array of size 10^5 whereas the problem statement states that the number of elements are 10^6. So, just change the array size to 10^6 and you will get rid of the RE.

But still, you code will get a Time Limit Exceeded (TLE) error because your sorting algorithm has 2 nested loops and hence has a complexity of O(N^2). You should use a faster sorting algorithm like Merge Sort or Quick Sort or Heap Sort that have an average complexity of O(N log N) or you can simply use the builtin sort() function in C++ available in <algorithm> header file.

To read more about sorting algorithms, go through the articles in the following links.

http://www.cplusplus.com/reference/algorithm/sort/

https://www.hackerearth.com/practice/algorithms/sorting/bubble-sort/tutorial/

4

Why do you think that Merge Sort, Quick sort and heap sort have an average complexity of O(log N)? A whole new world. They have average O(N log N). Infact, Quick sort has O(n^2) in worst case.

2 Likes
5

My bad, I know that these sorting algorithms have average time complexity of O(N log N), I thought I had written O(N log N) but wrote O(log N) by mistake. BTW, thanks for pointing it out.

6

Thanks. Was just trying to solve it using basic loops.
I will use these algorithms to escape time limit error.

1 Like