Al naibii de sortare

februarie 25, 2008

Cum OJI 2008 se apropie sunt nevoit să mă pregătesc câteva săptămâni în BC 3.1, cea ce înseamnă să fac probleme fără lejeritatea oferită de stl. Şi am început să lucrez la problema cârnaţi de pe IA în care era necesară o sortare.

Foloseam un quicksort şi implementarea era în genu:

  1. void quicksort(int st,int dr)
  2. {
  3. int m,i,j;
  4. inf aux;

  6. m = (st + dr) / 2;

  8. i = st; j = dr;

  10. do
  11. {
  12. while ( v[i].timp < v[m].timp ) i+=1;
  13. while ( v[j].timp > v[m].timp ) j-=1;
  14. if ( i <= j )
  15. {
  16. aux = v[i];
  17. v[i] = v[j];
  18. v[j] = aux;
  19. i+=1;
  20. j-=1;
  21. }
  22. } while ( i <= j );

  24. if ( i < dr ) quicksort(i,dr);
  25. if ( j > st ) quicksort(st,j);
  26. }

Bucaţile îngroşate evidenţiază greşeala mea fenomenală pe care am reuşit să o fac, la pivot reţineam poziţia nu valoarea lui şi aşa puteam să o pierd uşor.

Corectura necesară este următoarea:

m = v[(st + dr) / 2].timp;
while ( v[i].timp < m ) i+=1;
while ( v[j].timp > m ) j-=1;

De greşeală mi-am dat seama după ce m-a atenţionat un prieten, eu iniţial crezând că este quicksortul făcut total greşit, şi pe problemă am stat cam 4 ore şi nici nu mi-a trecut prin cap că s-ar putea ca sortarea să fie de vină numa când am folosit-o pe cea din stl, luând astfel 100.

Şi acum dacă tot am deschis subiectul sunt curios ce sortări mai folosiţi, mie mi se pare că heapsort ar fi o alegere bună, chiar cunosc pe cineva care numa heapsort foloseşte pentru sortare :) .

PS: scuzaţi-mi formatarea slabă de cod, nu prea ştiu cum stă treaba

Scris de binaryfire
Categorisit în Programming ·Tag-uri: , , ,

6 Răspunsuri sa “Al naibii de sortare”

  1. Mircea Dima said:
    februarie 25, 2008 at 11:55 am

    Da… heapsort ar fi o alternativa buna , mai ales ca operatiile cu heapurile se pot implementa recursiv. Insa… de ce sa ne complicam
    si sa pierdem timp implementand sortari cand le avem gata implementate (chiar si in BC 3.1).

    In stdlib.h exista functia qsort si se poate folosi si pentru structuri.

    De exemplu daca vrem sa sortam o multime de puncte dupa prima coordonata si in caz de egalitate dupa a2a putem proceda astfel:

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

    struct nod { int x, y;};

    inline int cmp(nod *a, nod *b)
    {
    if(a->x < x) return -1;
    if(a->x > b->x) return 1;
    if(a->y > b->y) return 1;
    if(a->y < y) return -1;
    return 0;
    }

    acum nu ne mai ramane decat sa apelam functia qsort astfel:

    qsort(a+1, n, sizeof(nod), (int(*)(const void *, const void *))cmp);

    O alta alternativa ar fi shell-sort ce are o complexitate O(nlog^2n) … dar in borland nu ne trebuie mai mult, nu? :D
    Partea proasta e ca nu am implementat niciodata… Din cate tin minte era in ginfo un articol.

  2. megabyte said:
    februarie 25, 2008 at 12:44 pm

    si eu tot qsort ul asta il folosesc, ii simlu de implementat si de inteles.Cei care folosesc heapsort pierd mult timp cu el, dar au un avantaj cand le pica o problema cu heap uri.
    Pacat de algoritmu asta ca are si dezavantaje si nu merge intotdeauna in N*log N, da se poate optimiza destul de bine daca alegi pivotul random. Am facu tun experiment sa vad la ce adancime ajunge un qsort normal cu pivot fix si unul cu pivot random:
    http://pastebin.com/f5b667bb1
    Ar mai fi merge_sort numai ca la OJI risti mult cu el.

  3. binaryfire said:
    februarie 25, 2008 at 12:44 pm

    Sincer să fiu nu am utilizat niciodată qsort-ul din stdlib.h, pare să fie mai comod decât să implementezi tu tot qsort-ul. Eu am implementat tot timpul qsort-ul de mână, până când am dat de stl … , pentru că simţeam că am mai mult control asupra codului pe care îl scriu.

  4. Mircea Dima said:
    februarie 25, 2008 at 12:50 pm

    In g++ qsort e implementat cu pivot aleator… in borland nush cum e

  5. Mircea Dima said:
    februarie 25, 2008 at 12:54 pm

    sau radix-sort (varianta bytesort) cu memorie O(2n+256) si timp
    O(kn) unde k=nr de bytes a celui mai mare numar :D
    ( e de cel putin 2 ori mai rapid decat sort din stl)

  6. Andrei Grigorean said:
    februarie 25, 2008 at 9:41 pm

    Qsort-ul din stdlib face treaba. E bun, spre deosebire de heap sort (HUUUOOOO). Pierzi timp si scrii mult cod => pot aparea buguri mai multe.

Lasă un Răspuns