Pagini: [1] 2 3 4   În jos
  Imprimă  
Ajutor Subiect: 028 Sortare prin comparare  (Citit de 35674 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« : Ianuarie 06, 2009, 19:38:35 »

Aici puteti discuta despre problema Sortare prin comparare din Arhiva educationala.
« Ultima modificare: Februarie 17, 2009, 02:38:28 de către Paul-Dan Baltescu » Memorat

Am zis Mr. Green
zalman
Strain
*

Karma: -11
Deconectat Deconectat

Mesaje: 31



Vezi Profilul
« Răspunde #1 : Ianuarie 24, 2009, 21:36:58 »

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?
Memorat
amadaeus
Client obisnuit
**

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #2 : Ianuarie 24, 2009, 23:13:09 »

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" wink
Memorat

"one of these days I'm going to cut you into little pieces..."
edu2004eu
Strain


Karma: -6
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #3 : Februarie 07, 2009, 14:46:57 »

Selection Sort ia numai 40 de pct, e prea incet. Probabil ca si Bubble Sort care e si mai incet.
Memorat
anna_bozianu
De-al casei
***

Karma: 5
Deconectat Deconectat

Mesaje: 111



Vezi Profilul
« Răspunde #4 : Februarie 11, 2009, 16:34:59 »

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?
Memorat
05_Yohn
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #5 : Februarie 14, 2009, 18:05:33 »

 sad
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  Thumb up
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #6 : Februarie 14, 2009, 18:18:42 »

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.
Memorat

Am zis Mr. Green
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #7 : Februarie 14, 2009, 21:05:06 »

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.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #8 : Februarie 15, 2009, 08:49:19 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #9 : Februarie 15, 2009, 09:46:04 »

Pai atunci de ce nu sortare prin comparare. Suna dubios comparare directa.
Memorat
raduzer
Client obisnuit
**

Karma: 62
Deconectat Deconectat

Mesaje: 71



Vezi Profilul
« Răspunde #10 : Februarie 18, 2009, 10:35:57 »

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

Karma: 28
Deconectat Deconectat

Mesaje: 93



Vezi Profilul
« Răspunde #11 : Februarie 26, 2009, 00:12:54 »

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

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

"one of these days I'm going to cut you into little pieces..."
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #12 : Martie 09, 2009, 13:43:07 »

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.
Memorat
alexthero
De-al casei
***

Karma: 121
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #13 : Martie 09, 2009, 14:23:31 »

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];
Memorat

Tine minte ca mintea conduce pumnu, nu invers
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #14 : Martie 09, 2009, 16:10:17 »

Si cum aleg un numar aleatoriu, dau random()?..........
Memorat
alexthero
De-al casei
***

Karma: 121
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #15 : Martie 09, 2009, 16:32:46 »

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)
...
...
Memorat

Tine minte ca mintea conduce pumnu, nu invers
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #16 : Martie 09, 2009, 17:17:06 »

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

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #17 : Martie 09, 2009, 17:40:24 »

Nu implementeaza nimeni introsort de mana, de asta ai STL Smile
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #18 : Martie 09, 2009, 17:55:34 »

hm ......stiu putine din STL, n-am apucat sa  intru in aprofunzime Sad,  imi  poti arata  cum se face plsz. 
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #19 : Martie 09, 2009, 18:05:13 »

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.
Memorat
c_e_manu
Nu mai tace
*****

Karma: 56
Deconectat Deconectat

Mesaje: 243



Vezi Profilul
« Răspunde #20 : Martie 09, 2009, 18:07:44 »

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
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #21 : Martie 09, 2009, 18:50:24 »

multumesc Very Happy
Din cate vad  qosrt  este mai incet decat sort, vorbind de functiile de sortare Very Happy
« Ultima modificare: Martie 09, 2009, 20:07:12 de către alexandru » Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #22 : Martie 09, 2009, 20:28:11 »

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 .
Memorat
florin_marius90
Strain


Karma: -15
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« Răspunde #23 : Martie 23, 2009, 06:10:53 »

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 Think . Sa fie oare de la alegerea elementului de mijloc?
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #24 : Martie 23, 2009, 13:43:00 »

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.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1] 2 3 4   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines