#include <stdio.h>
int main(void) {
int n,i;
scanf("%d",&n);
int a[n];
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<n;i++)
{
if(a[i]<a[i-1])
{
int temp=a[i];
a[i]=a[i-1];
a[i-1]=temp;
i=0;
}
}
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
Time limit is getting exceeded for my code.i tried optimising the sort.What else can i change in it?
Try quick sort, since according to me your sorting technique will take O(n^2) time , you can make it better by quick or merge sort O(nlogn) time.
The following code fragment:
is creating the bottleneck for the code. Each time an element smaller than the previous element is found in the array, the loop starts from 0 again thereby traversing the whole array from beginning again. Now for example if we input an array which has input in pure descending order, the code would run in effectively O(n^2) time which will cause TLE. You should read and learn about merge-sort here , that would reduce the time comlexity of sorting to O(nlogn) which can remove the TLE.
Happy Coding!
Implementing codes by yourself is a best practice but in case you don’t want to implemeny merge sort by yourself then you can use algorithm library of c++, will does this for you.
Algorithm library have already defined sort function you just need to provide the first and last pointer of your array in order to sort that ; P