Titlul: QSort Scris de: Tabara Mihai din Ianuarie 31, 2007, 23:10:39 Ma poate lamuri si pe mine cineva cu o chestie legata de QSort()
Foloseam la problema Patrate3 o sortare pentru puncte. Aceasta sortare merge prost pe ultimele 5 teste si iau numai 75. Cod: double pivot = a[st].x; Iar daca inlocuiesc pe a[st].y in QSort cu un double pivot2 = a[st].y declarat la inceput merge de 100. Cod: double pivot = a[st].x; Titlul: Raspuns: QSort Scris de: Andrei Grigorean din Ianuarie 31, 2007, 23:47:03 nu prea am avut rabdare sa citesc codul, insa tu nu modifici in timpul ciclului a[st]?
Titlul: Raspuns: QSort Scris de: Tabara Mihai din Februarie 01, 2007, 00:15:52 nu prea am avut rabdare sa citesc codul, insa tu nu modifici in timpul ciclului a[st]? Pai se modifica numai cand apelez QSort-ul din nou, dar atunci il apelez cu parametrii si are grija cand intra in QSort ca a[st].x sa fie noul stanga ( apelat din QSort-ul anterior ). :-s Titlul: Raspuns: QSort Scris de: Valentin Stanciu din Februarie 01, 2007, 07:42:24 ar trebui sa ne arati tot codul de la Qsort.. asa nu pare sa fie nici o problema..
a[st].y ce tip este? Titlul: Raspuns: QSort Scris de: Tabara Mihai din Februarie 02, 2007, 13:35:25 ok :ok:
Asta e varianta care merge de 100 cu pivot2 in loc de a[st].y in functia QSort. Cod: double pivot = a[st].x; Asta e sursa care buseste ultimele 5 teste ca nu sorteaza bine. Cod: double pivot = a[st].x; Titlul: Raspuns: QSort Scris de: Valentin Stanciu din Februarie 02, 2007, 14:56:52 ok, cred ca ti-am gasit problema
nu ar trebui sa fie: int i = st + 1, j = dr - 1; ?? Exista cazul cand do { i++;} while (...) o sa iti creasca i cu o unitate si o sa devina i == st. (j nu conteaza ce e) Tu o sa inlocuiesti a[ i ] cu a[j] (sau mai bine zis a[st] cu a[j]).. si uite asa a[st] nu mai este ce era la inceput. In momentul cand scrii pivot2 = a[st].y, tu tii minte valoarea respectiva. Pe parcurs intradevar, o sa se schimbe a[st] cu un a[j], dar tu o sa compari in continuare dupa pivot2! Qsort merge bine daca folosesti pivot2 ca o sa obtii o partitionare dupa o valoare fixa. Daca nu folosesti pivot2, acea valoare din a[st] (mai exact a[st].y) o sa se schime si o sa shimbi elementul dupa care faci partitionarea. Sper ca te-am lamurit :D Titlul: Raspuns: QSort Scris de: Tabara Mihai din Februarie 02, 2007, 17:23:41 ok, cred ca ti-am gasit problema nu ar trebui sa fie: int i = st + 1, j = dr - 1; ?? Nu cred...pentru ca oricum apelez QSort( 1, n ) ( sirul contine elementele de la 1 la n ) si deci initial i este 0 si cand fac do { i++; } merge fix pe prima pozitie deci incepe bine. Oricum am inteles ce ai zis in rest si m-am lamurit.Valoarea aia a[st].y se modifica in program [ :aha:]si trebuie tinuta tot timpul sub forma unei variabile. Sper ca te-am lamurit :D Da.Ms f mult =D> :peacefingers: |