turbo sort

general
, ,
1

hi friends;

#include <stdio.h>
int main(int argc, char *argv[])
{
int a[100000],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

2

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.

3

thanks for your answer ;

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

thanks

4

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.

5

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.

6

thanks guys for your answers;

it’s Works now;

7

I used shell sort, and that gave me AC. Shell sort is very close to insertion sort and bubble sort and the code is very efficient. Found it easier to understand than counting sort and quick sort (P.S. I’m a beginner) and am looking forward to stick to shell sort for most of my work.