11462 - Age Sort

[shawon10]

why Time Limit Exceed?

Code: Select all

#include <stdio.h>
int main()
{
    int n,*a,i,j,t;

    while(scanf("%d",&n)!=EOF)
    {
        a=(int*)malloc(sizeof(int)*n);
        if(n==0)
        {
            break;
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",(a+i));
        }
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                if(*(a+i)>*(a+j))
                {
                      t=*(a+j);
                    *(a+j)=*(a+i);
                    *(a+i)=t;
                }
            }
        }
        for(i=0;i<n;i++)
        {
            printf("%d ",*(a+i));
        }
        printf("\n");
    }
    return 0;
}

[brianfry713]

Read this thread.

[shawon10]

Read this thread.

Yes.. for 100000 this code is not running. but how can i fix Time Limit Exceed in this code?

[brianfry713]

Dears, only for couriously, there are here some performances tests that I can relate for this problem:

Método Execution time
bubleSort TLE (> 5 seconds)
Qsort Stl with cin / cout 1.072
Quicksort with scanf / printf 0.786 secs (maybe not so good qsort!?)
Mergesort with scanf / printf 0.656 secs (with a best mergesort)
qsort Stl [ sort(age,age + tam); ] 0.596 secs
Counting Sort (with vector) 0.473 secs (18 º world time)
Counting Sort (without vector) 0.456 secs
Counting Sort with fast input 0.343 seconds (13 º )
Counting Sort with fread/fwrite 0.204 seconds (10 º )
Counting Sort fread/fwrite optimized 0.156 (8º)
Counting Sort fread optimized /fwrite optimized 0.052 (2º) same that 1º mundial place.

[MI Sabic]

can anyone help me???
why TLE??

Code: Select all

#include<stdio.h>
#include<stdlib.h>

int divide(int arr[], int start, int end)
{
    int pivot;
    if(start>=end)
        return ;
    else
    {
        pivot=sort(arr,start,end);
        divide(arr,start,pivot-1);
        divide(arr,pivot+1,end);
    }
}

int sort(int arr[], int start, int end)
{
    int i,j,pivot,rec=1;
    pivot=arr[start];
    i=start;
    j=end;
    while(i<j)
    {
        if(rec)
        {
            if(arr[j]<pivot)
            {
                arr[i]=arr[j];
                i++;
                rec=0;
            }
            else
                j--;
        }
        else
        {
            if(arr[i]>pivot)
            {
                arr[j]=arr[i];
                j--;
                rec=1;
            }
            else
                i++;
        }
    }
    arr[j]=pivot;
    return j;
}

int main()
{
    int i,j,n,temp,*arr;
    while(scanf("%d",&n)==1)
    {
        arr=malloc(n*sizeof(int));
        if(n==0)
            break;
        for(i=0; i<n; i++)
            scanf("%d",&arr[i]);
        divide(arr,0,n-1);
        for(i=0; i<n; i++)
        {
            printf("%d",arr[i]);
            if (i<(n-1))
                printf(" ");
        }
        printf("\n");
        free(arr);
    }
    return 0;
}