028 Sortare prin comparare

[•pauldb]

Aici puteti discuta despre problema Sortare prin comparare din Arhiva educationala.

[•zalman]

I need help!!
Am incercat vreo 5-6 sortari pana acuma si cum era de asteptat nu prea merg.
Una ia 100 - Introsortul din STL.
restul in cel mai bun caz 40.
Quicksort`urile pe care le-am incercat se apropie insa tot depasesc timpul la cateva teste.
Am o mica mare nelamurire. Algoritmul din articol (Merge Sort) da raspuns gresit pe testele "aproape sortate". De ce?
Cum se poate rezolva problema?

[•amadaeus]

Am incercat vreo 5-6 sortari pana acuma si cum era de asteptat nu prea merg.
Una ia 100 - Introsortul din STL.
restul in cel mai bun caz 40.

Depinde mult de ce algoritmi ai incercat. Daca sunt neoptimi (Bubble Sort, Insertion Sort, Selection Sort etc) este normal sa nu ia punctaj maxim. Introsort, pe de alta parte, este unul dintre cei mai eficienti algoritmi de sortare cunoscuti si ar trebui sa se comporte cel mai bine.

Quicksort`urile pe care le-am incercat se apropie insa tot depasesc timpul la cateva teste.

Quicksort-urile trebuie implementate atent pentru punctaj maxim. Cu toate acestea, varianta din libraria standard C (functia qsort) obtine 100 de puncte, chiar daca nu este din cate stiu eu (aici s-ar putea sa gresec) cea mai fericita varianta de quicksort. Incearca sa te uiti la prezentarile de care vorbeam in rubrica 'Solutii' si sa imbunatatesti versiunile tale de quicksort.

Am o mica mare nelamurire. Algoritmul din articol (Merge Sort) da raspuns gresit pe testele "aproape sortate". De ce?

Merge Sort-ul din articol ia 100 de puncte daca e implementat atent. O sursa gasesti aici.

Cum se poate rezolva problema?

Cu orice algoritm de aici care are O(n log n) pe coloana "Worst"

[•edu2004eu]

Selection Sort ia numai 40 de pct, e prea incet. Probabil ca si Bubble Sort care e si mai incet.

[•anna_bozianu]

Am trimis o sursa in care am utilizat un radixsort pe biti. Ulterior am descoperit ca avea o eroare (vezi http://infoarena.ro/job_detail/249770 la linia 18 ar fi trebuit sa am d=dr-st+2 in loc de d=dr+1). Cu toate acestea sursa "defecta" mi-a scos 100 de puncte.
Nu reusesc sa inteleg de ce. Poate cineva sa se uite un pic pe sursa?

[•05_Yohn]

 
am si eu o intrebare..
fac un arbore binar si in parcurg in inordine(srd)
cu o sursa in pascal pot sa iau mai mult de 40 pct??
ms 

[•pauldb]

Problema ta nu vine de la faptul ca implementezi in Pascal. Complexitatea ta in cazul cel mai defavorabil este O(N^2). Ai putea reduce la O(NlogN) daca ai folosi un arbore binar de cautare echilibrat.

[•Cosmin]

De ce ii zice la problema asta "sortare prin comparare directa"? Nu am mai auzit denumirea asta pe nicaieri, si nu cred ca e bine sa inventam noi denumiri.

[•wefgef]

Cred ca din cauza ca pentru a sorta compari elementele sirului (in contrast cu radixsort, de exemplu).

[•Cosmin]

Pai atunci de ce nu sortare prin comparare. Suna dubios comparare directa.

[•raduzer]

Am facut evalul sa crape. Eroarea provine din faptul ca nu las spatiu la printare. (JOB #261387)

[•amadaeus]

Am facut evalul sa crape. Eroarea provine din faptul ca nu las spatiu la printare. (JOB #261387)

S-a rezolvat
http://infoarena.ro/job_detail/266726

[•alexandru92]

functia  qsort() din stdlib.h e mai rapida decat Qsort-ul scris manual ??
Am scris doua  surse  unua cu Qsort() scris de mine, a luat 40 ,aici e sursa, si una cu qsort() din stdlib.h si ia 100 pct,scris aici.

[•alexthero]

Incearca sa alegi un pivot random aici:

Cod:

long sort(long st,long dr)  
{  
long x=v[st];  
while(st<dr)  
    {while(st<dr&&v[dr]>=x) dr--;
...

In loc de v[st] alege un alt element aleator din intervalul [st,dr]. Cel mai simplu ar fi sa interschimbi elementul de pe pozitia st cu un element de pe o pozitie aleatoare din [st,dr] inainte de x = v[st];

[•alexandru92]

Si cum aleg un numar aleatoriu, dau random()?..........

[•alexthero]

Cod:

int poz = st + rand() % (dr - st + 1);
long aux = v[poz]; v[poz] = v[st]; v[st] = aux;

long x = v[st];
while(st < dr) 
...
...

[•alexandru92]

Multumesc  ..mai am putin de optimizat ...tot i-au 2 TLE, hm daca afiseaza corect timpul depasesc cu 4ms 
Poti sa-mi recomanzi o implementare a  intrasort, am cautat pe google dar nu gasesc

[•wefgef]

Nu implementeaza nimeni introsort de mana, de asta ai STL

[•alexandru92]

hm ......stiu putine din STL, n-am apucat sa  intru in aprofunzime ,  imi  poti arata  cum se face plsz. 

[•sima_cotizo]

Nici nu m-am mai dus pe google, am incercat direct pe wiki si am urmat primul link extern:
http://ralphunden.net/?q=a-guide-to-introsort
Cred ca e destul de bine explicat si are si o implementare din cate vad.

[•c_e_manu]

Cod:

#include<algorithm>

using namespace std;

int v[100];

sort(v,v+n);//sau sort(v+1,v+1+n); daca folosesti v-ul de la 1 si nu de la 0

mai poti adauga o functie de comparare pentru a sorta dupa numite valori dintr-o structura de exemplu... dar asta s-a mai discutat aici : http://infoarena.ro/forum/index.php?topic=3706.0

[•alexandru92]

multumesc
Din cate vad  qosrt  este mai incet decat sort, vorbind de functiile de sortare

[•toni2007]

Am implementat eu introsort in c mai demult, cand nu lucram pe c++ (mi-a luat ceva timp si cu copy paste in multe locuri), dar nu am stiut exact sa setez adancimea qsortului, astfel incat imi iese pe 2 teste din timp. Sursa e aici .

[•florin_marius90]

Sal ! help miii ! am implementat un quicksort in pascal si din cele 4 grupe de teste nu exista o grupa in care sa raspund corect la toate cele 4 teste/grupa, se incadreaza in timp la toate dar cand iau 0 cand iau 5 pe testuletz => 0 pct total . Sa fie oare de la alegerea elementului de mijloc?

[•wefgef]

Problema ta provine de la faptul ca atunci cand iti alegi pivotul iti fixezi pozitia lui in vector. Ar trebui sa iti fixezi valoarea. In sursa ta ar trebui sa fie:

Cod:

        i:=s; j:=d; x:=a[(s+d) div 2];
        repeat
          while a[i]<x do i:=i+1;
          while a[j]>x do j:=j-1;

Primeai raspuns gresit din cauza ca in interiorul instructiunii while valoarea de pe pozitia (s+d) div 2 se poate schimba.