QSort

[•Tabara]

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;
     
     int i = st - 1, j = dr + 1;
     do
     {
         do { i++; } while ( (pivot - a[i].x) >= eps || (fabs( pivot - a[i].x)< eps && (a[st].y - a[i].y)>= eps ) );
         do { j--; } while ( (a[j].x - pivot ) >= eps || (fabs( a[j].x - pivot)< eps && (a[j].y- a[st].y ) >= eps ) );
.....

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;
     [b]double pivot2 = a[st].y;[/b]
     int i = st - 1, j = dr + 1;
     do
     {
         do { i++; } while ( (pivot - a[i].x) >= eps || (fabs( pivot - a[i].x)< eps && (pivot2 - a[i].y)>= eps ) );
         do { j--; } while ( (a[j].x - pivot ) >= eps || (fabs( a[j].x - pivot)< eps && (a[j].y - pivot2 ) >= eps ) );

Unde se creeaza diferenta ?

[•wefgef]

nu prea am avut rabdare sa citesc codul, insa tu nu modifici in timpul ciclului a[st]?

[•Tabara]

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

 

[•svalentin]

ar trebui sa ne arati tot codul de la Qsort.. asa nu pare sa fie nici o problema..
a[st].y ce tip este?

[•Tabara]

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;
     double pivot2 = a[st].y;
     int i = st - 1, j = dr + 1;
     do
     {
         do { i++; } while ( (pivot - a[i].x) >= eps || (fabs( pivot - a[i].x)< eps && (pivot2 - a[i].y)>= eps ) );
         do { j--; } while ( (a[j].x - pivot ) >= eps || (fabs( a[j].x - pivot)< eps && (a[j].y - pivot2 ) >= eps ) );
         if ( i <= j )
         {
              aux = a[i];
              a[i] = a[j];
              a[j] = aux;
         }
     } while ( i <= j );
     if ( i < dr ) QSort ( i, dr );
     if ( st < j ) QSort ( st, j );

Asta e sursa care buseste ultimele 5 teste ca nu sorteaza bine.

Cod:

double pivot = a[st].x;
     
     int i = st - 1, j = dr + 1;
     do
     {
         do { i++; } while ( (pivot - a[i].x) >= eps || (fabs( pivot - a[i].x)< eps && (a[st].y - a[i].y)>= eps ) );
         do { j--; } while ( (a[j].x - pivot ) >= eps || (fabs( a[j].x - pivot)< eps && (a[j].y - a[st].y ) >= eps ) );
         if ( i <= j )
         {
              aux = a[i];
              a[i] = a[j];
              a[j] = aux;
         }
     } while ( i <= j );
     if ( i < dr ) QSort ( i, dr );
     if ( st < j ) QSort ( st, j );

[•svalentin]

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

[•Tabara]

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 [ ]si trebuie tinuta tot timpul sub forma unei variabile.

Sper ca te-am lamurit

Da.Ms f mult