# Turbo sort

hi friends;

#include <stdio.h>
int main(int argc, char *argv[])
{
int a,i,k,dim,max;
int p;

``````scanf("%d",&dim);
for(i=0;i<dim;i++)
scanf("%d",&a[i]);

for(i=0,k=0;i<dim;i++){
max=i;
for(k=i;k<dim;k++){
if(a[max]<a[k])
max=k;
}
p= a[max];
a[max] = a[i];
a[i] = p;
}
for(i=0;i<dim;i++)
printf("%d\n",a[i]);
``````

return 0;
}
hi, i tried to submit this code cut it said to me “runtime…”;
i wish that you can help me ;
thanks

Your algo runs for a time O(dim^2).

I can see that the value for dim can be upto 10^6. This leads to a running time of 10^12 !!

This will certainly lead to a TLE.

Try to run it in O(dim) or reduce the size of dim to around 10^3 - 10^4.

can you please explain more i’m just a bignner and i didn’t understand you;

thanks

the time limit for this problem is limited which you are exceeding due to large number of operations inside loop if given large input as in constraints.try to reduce the number of operations by using a better approach of sorting.

You have implemented bubblesort, which has a running time of O(n^2), where n is the array size. Since n can be upto 10^6, a bubblesort implementation will result in a O(10^12) solution. Since the maximum number of iterations that can be done in 1 second (the time constraint) are ~10^8, your code will result in TLE. Try a sorting algorithm taking < O(n^2) time, like quicksort or mergesort. Even the inbuilt std::sort for C++ and qsort for C work fine.

manjunath1996: Sorting cannot be done in O(n) time without having some prerequisite knowledge about the array elements. Radix sort and counting sort work in O(n) because they have some preconditions that must be fulfilled.