qsort

[•PetruD]

Am si eu o intrebare legata de functia predefinita qsort. Cum fac daca vreau sa sortez un vector de struct folosind qsort? Spre exemplu am coordonatele unor segmente pe o dreapta (x1, x2) si vreau sa sortez segmentele crescator dupa x1 si descrescator dupa x2.

Multumesc anticipat.

[•SpiderMan]

Esti in Pascal sau in C++ ? Daca esti in C++, stii STL ?

[•deneo]

Din cate am vazut esti pe Pascal ... dar intrebarea sigur e pentru C++.
Fiindca asta ma intereseaza si pe mine am cautat pe Google (la gimnaziu nu avem STL ) si uite ce am gasit:

Cod:

/* an example of struct */ 
struct st_ex { 
    char product[16];
    float price;
};
 
/* qsort struct comparision function (price float field) */ 
int struct_cmp_by_price(const void *a, const void *b) 
{ 
    struct st_ex *ia = (struct st_ex *)a;
    struct st_ex *ib = (struct st_ex *)b;
    return (int)(100.f*ia->price - 100.f*ib->price);
	/* float comparison: returns negative if b > a 
	and positive if a > b. We multiplied result by 100.0
	to preserve decimal fraction */ 
 
} 
 
/* qsort struct comparision function (product C-string field) */ 
int struct_cmp_by_product(const void *a, const void *b) 
{ 
    struct st_ex *ia = (struct st_ex *)a;
    struct st_ex *ib = (struct st_ex *)b;
    return strcmp(ia->product, ib->product);
	/* strcmp functions works exactly as expected from
	comparison function */ 
} 

structura si exemple de functii de cmp
cred ca e clar acum

[•SpiderMan]

Mai frumos cu sort-ul din STL, mai rapid + mai usor de implementat. Faci structura ca si pair, si apoi sortezi.

Cod:

pair < int, int > S ;
sort ( S + 1, S + N + 1 ) .

[•PetruD]

@deneo:
Mersi mult! Si nu, nu (mai) sunt pe Pascal de multa vreme.

Mai frumos cu sort-ul din STL, mai rapid + mai usor de implementat. Faci structura ca si pair, si apoi sortezi.

Cod:

pair < int, int > S ;
sort ( S + 1, S + N + 1 ) .

Nu stiu sa lucrez cu template-uri ... Dar... ca veni vorba, functia sort este mai eficienta decat qsort?

[•deneo]

eu folosesc STL-ul in mod normal. si majoritatea stim sa folosim STL-ul (macar sort-ul din STL)
dar daca la gimnaziu se foloseste borland ca compilator de unde STL  
cand e greu, ne adaptam

PS. era mult mai util postul tau daca scriai si o functie cmp care arata cum se foloseses-te un vector de perechi

[•deneo]

@deneo:
Mersi mult! Si nu, nu (mai) sunt pe Pascal de multa vreme.

Mai frumos cu sort-ul din STL, mai rapid + mai usor de implementat. Faci structura ca si pair, si apoi sortezi.

Cod:

pair < int, int > S ;
sort ( S + 1, S + N + 1 ) .

Nu stiu sa lucrez cu template-uri ... Dar... ca veni vorba, functia sort este mai eficienta decat qsort?

Da este ... functia sort este mai rapida decat qsort
daca vrei sa aflii mai multe despre algortmii de sortare uite un studiu. si o sa afli si de ce e mai rapid sort-ul ca qsort-ul
http://www.worldit.info/files/Studiu%20asupra%20algoritmilor%20de%20sortare.pdf

[•SpiderMan]

@adrian, sa stii ca NU TREBUIE FUNCTIA CMP la pair, de aceea nu am pus nicio functie. El sorteaza automat dupa primul paramentru al pair-ului, adica .first.

[•soriyn]

Da, sort este mai eficienta.

Si nu trebuie sa folosesti pair. Poti sa faci ceva de genul :

Cod:

typedef struct 
{
	int x,y;
}punct;

punct pt[100];

bool cmp(punct a,punct b)
{
	if(a.x<b.x) return 1;
	if(a.x==b.x) if(a.y<b.y) return 1;
}

int main()
{
   sort(pt+1,pt+n+1,cmp);
}

[•deneo]

dar daca vreau sa sortez dupa second ?
 

Am si eu o intrebare legata de functia predefinita qsort. Cum fac daca vreau sa sortez un vector de struct folosind qsort? Spre exemplu am coordonatele unor segmente pe o dreapta (x1, x2) si vreau sa sortez segmentele crescator dupa x1 si descrescator dupa x2.

Multumesc anticipat.

daca observi intrebarea initiala el vrea sa sorteze in functie de first si de second nu doar dupa first. eu pe principiul asta am mers cand am zis ca trebuia si cmp
si nu trebuia sa scrii cu litere mari

[•PetruD]

@Adrian:

Sunt clasa a noua.

[•deneo]

Daca nu scrii pe profil de unde vrei sa stiu   ?
Oricum daca nu esti in situatia mea iti recomand sort-ul din stl. E mai simplu, mai bun, mai rapid, mai flexibil, ce ai dori mai mult?
Ca sa aprofundezi uita-te pe articolul asta: http://infoarena.ro/stl (cred ca il stii, dar ti-l readuc aminte)
Daca vrei STL sa stii ca lumea iti recomand cartea lui Constantin Galatan - Introducere in Standard Template Library

[•SpiderMan]

@adrian Din nou iti repet, daca nu stii nu te baga, pair SORTEAZA DUPA FIRST SI IN CAZ E EGALITATE DUPA SECOND, DACA VREI INVERS N-AI DECAT SA INVERSEZI SECOND CU FIRST, ADICA SECOND DEVINE FIRST SI INVERS.

[•soriyn]

Pai el vrea crescator dupa first si,in caz de egalitate, descrescator dupa second 

[•deneo]

@robert eu stiu ca daca vrei sa inversezi second cu first iti trebuie o functie cmp. si daca vrei sa sortezi crescator dupa first si descrescator dupa second cum faci ?
daca stii tu cum scuza-ma de nestiinta mea. si te rog hai ca incheiem cu discutia asta tampita pe o functie cmp (de fapt te rog raspunde la intrebarea mea   )

[•SpiderMan]

Daca vrei sa inversezi second cu first faci asta de la citire, gen :

Cod:

for ( int i = 1; i <= N; ++i ) {
    scanf ( "%d %d", &V[i].y, &V[i].x ) ;
}

Unde x = first si y = second. Astfel, coloana a doua o sa devina first si prima coloana o sa devina second .

[•soriyn]

Spre exemplu am coordonatele unor segmente pe o dreapta (x1, x2) si vreau sa sortez segmentele crescator dupa x1 si descrescator dupa x2.

Multumesc anticipat.

Nici nu 

[•deneo]

Asta am cerut eu - adica mi-am argumentat ideea. Da in caz de egalitate la first sa sorteze descrescator la second.
Si cu inversarea second cu first de la citire nu prea sunt de acord. Adica ma va incurca in crearea algoritmului (poate uit ca is inversate etc. ). Pe mine, tu poate nu ai probleme din astea. gata hai ne oprim

[•SpiderMan]

Da, si faza cu crescator / descrescator era doar "un exemplu", eu am dat cazul general , pentru ca Sorin a pus cu cmp .

[•PetruD]

Trebuie sa declar un header, ceva? Ca vad ca nu imi compileaza.

[•deneo]

Pune codul ca sa-ti zic ce trebuie sa mai pui (header #include<algorithm> pt. sort )

[•soriyn]

si pune si

Cod:

  using namespace std;

[•PetruD]

Multumesc.