028 Sortare prin comparare

[•skull]

Am obtinut imbunatatiri semnificative la timpi dar tot la 80 pct am ramas .

[•alexandru92]

Fa functiile iterativ

[•skull]

Din moment ce recursivitatea nu apeleaza aceeasi functie de 2 ori(pentru a pierde timp), de ce ar merge mai rapid iterativ? In plus e mult mai elegant recursiv.

[•popoiu.george]

@skull prin recursivitate programul lucreaza cu stiva, si de aici s-ar putea sa fie mai incet programul.

[•zsee]

ms mult Cosmin!

Nu stiu cum nu am mai auzit de asta.... dar e foarte fain, a taiat timpul de executie la jumate
http://infoarena.ro/job_detail/409234

[•skull]

Am folosit settextbuf si pt. fisierul de iesire si deja au aparut timpi mult mai buni. Merci Cosmin & Alexandru.

LE: Functia settextbuf "pacaleste" doar compilatorul folosit pe infoarena sau si pe cele de la oji/oni? Ca doar o asemenea imbunatatire de timp poate face diferenta.

[•zsee]

cred ca la oni compilatorul e tot fpc si ar trebui sa mearga

[•alexandru92]

Am folosit settextbuf si pt. fisierul de iesire si deja au aparut timpi mult mai buni. Merci Cosmin & Alexandru.

LE: Functia settextbuf "pacaleste" doar compilatorul folosit pe infoarena sau si pe cele de la oji/oni? Ca doar o asemenea imbunatatire de timp poate face diferenta.

IDE-ul de la oji/oni e Free Pascal, deci da

[•Cosmin]

@alexandru free pascal nu e ide, ci e compilator.

settextbuf nu parseaza citirea ci in loc sa citeasca caracter cu caracter citeste o portiune de marimea bufferului, asta face citirea de pe disc mai eficienta.

[•ana.z]

Cod:

#include<stdio.h>
long n,j,i,aux,v[50001];
int main()
{
freopen("algsort.in","r",stdin);
freopen("algsort.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld",&v[i]);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(v[j]<v[i])
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
}
for(i=1;i<=n;i++)
printf("%ld ",v[i]);
return 0;
}

  Imi da TLE-uri cam pe jumatate din teste!Nu inteleg de ce....

[•SpiderMan]

Din cate vad eu acea sortare nu esti "optima" ... Iti trebuie o sortare in O ( N logN ) .

[•PlayLikeNeverB4]

Chiar nu inteleg de ce nu iau 100... sau macar punctaj mai mare.
http://infoarena.ro/job_detail/495408?action=view-source

Edit: Nu conteaza. Construiam heap-ul gresit. Faceam upheap de jos in sus. Stupid, stupid me.

P.S.: Quicksort sux !

[•c_sebi]

La multi ani!

A incercat cineva sortare pe liste inlantuite? Am incercat un Merge sort pe liste simplu inlantuite, dar am luat 80p. Vreo idee cum as putea imbunatati solutia? http://infoarena.ro/job_detail/518727
Mersi!

[•brucewillis]

din cate stiu eu nu poti sorta eficient liste.

[•blustudio]

Ati putea sa-mi spuneti si mie ce s-ar putea optimiza la http://infoarena.ro/job_detail/587011 deoarece nu ia 100p, iar acelasi algoritm scris in Pascal ia punctajul maxim http://infoarena.ro/job_detail/587028 ?

[•SpiderMan]

In sursa Cpp, incearca sa inlocuiesti unsigned long long cu int si vezi rezultatele .

[•caen1]

Cu qsort-ul din C nu am mai reusit sa iau 100. E in regula, sau ar trebui sa il adaug la lista cu limite care trebuie calibrate?

Job 1: http://infoarena.ro/job_detail/615319
Job 2: http://infoarena.ro/job_detail/642627

[•Laura_M]

Buna!
Am trimis urmatoarea problema si imi spune ca fisierul de iesire e corupt si o chestie cu killed by signal 11. Imi puteti spune ce nu e in regula?

Cod:

#include <iostream>
#include <fstream>

using namespace std;

int a[100], n;

void interclasare (int i, int m, int j)
{
     int b[100];
     int x=i;
     int k=1; 
     int y=m+1;
     while ((x<=m)&&(y<=j))
       if (a[x]<a[y])
           b[k++]=a[x++];
       else 
           b[k++]=a[y++];
     while (x<=m)
           b[k++]=a[x++];
     while (y<=j)
           b[k++]=a[y++];
     int t=i;
     for (k=i; k<=(j-i)+1; k++)
          {a[t]=b[k];
           t++;}
}

void div_imp (int i, int j)
{
     if (i<j)
        {int m=(i+j)/2;
         div_imp(i,m);
         div_imp(m+1,j);
         interclasare(i,m,j);}
}

int main()
{
    int a[100], p=0, q=0;
    fstream f("algsort.in", ios::in);
    while (!f.eof())
      {p++;
       f>>a[p];
       q++;}
    for (p=1; p<q; p++)
        cout<<a[p]<<" ";
    f.close();
    div_imp(1,n);              
    fstream g("algsort.out", ios::out);
    for (p=1; p<q; p++)
         g>>a[p];
    g.close();
    return 0;     
}       

                                               

job #654373

Editat de admin: Foloseste tagul "code" cand postezi surse.

[•SpiderMan]

Din cate vezi, nu ai 100 elemente, ai 500.000 . Pune limita 500005 si e suficient .

[•Laura_M]

Multumesc, SpiderMan; imi scapase asta. Dar imi spune in continuare ca fisierul de iesire e corupt. Nu inteleg de ce. Vreo sugestie?

[•SpiderMan]

Cod:

 for (p=1; p<q; p++)
         g>>a[p];

Aici nu cumva e <= q in for ? Daca nu e asta, o sa iau codul sa ma uit pe el .

[•Laura_M]

Am modificat si da aceeasi eroare. Ai putea sa te uiti pe ea putin, te rog?

[•PlayLikeNeverB4]

- Variabila n ti-e neinitializata (ma rog, e 0, dar nu cred ca asta iti doresti)
- Din cate vad tu introduci in sirul de numere si numarul de pe prima linie a fisierului (adica numarul care ar trebui sa reprezinte numarul de elemente ale sirului). Poti citi acel numar separat si apoi citirea sirului cu un for.

[•Laura_M]

Multumesc, merge acum

[•reking]

Deci cel mai eficient algoritm de sortare este 'Merge sort'