infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Petru Dimitriu din Aprilie 12, 2011, 11:18:06



Titlul: qsort
Scris de: Petru Dimitriu din Aprilie 12, 2011, 11:18:06
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.


Titlul: Răspuns: qsort
Scris de: Simoiu Robert din Aprilie 12, 2011, 12:53:53
Esti in Pascal sau in C++ ? Daca esti in C++, stii STL ?


Titlul: Răspuns: qsort
Scris de: Adrian Craciun din Aprilie 12, 2011, 13:33:11
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 :eyebrow: ) 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 :)


Titlul: Răspuns: qsort
Scris de: Simoiu Robert din Aprilie 12, 2011, 13:53:54
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 ) .


Titlul: Răspuns: qsort
Scris de: Petru Dimitriu din Aprilie 12, 2011, 14:06:44
@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?


Titlul: Răspuns: qsort
Scris de: Adrian Craciun din Aprilie 12, 2011, 14:08:40
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  :eyebrow:
cand e greu, ne adaptam :D

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



Titlul: Răspuns: qsort
Scris de: Adrian Craciun din Aprilie 12, 2011, 14:12:01
@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


Titlul: Răspuns: qsort
Scris de: Simoiu Robert din Aprilie 12, 2011, 14:13:03
@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.


Titlul: Răspuns: qsort
Scris de: Sorin Rita din Aprilie 12, 2011, 14:15:41
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);
}


Titlul: Răspuns: qsort
Scris de: Adrian Craciun din Aprilie 12, 2011, 14:17:25
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 :)


Titlul: Răspuns: qsort
Scris de: Petru Dimitriu din Aprilie 12, 2011, 14:21:51
@Adrian:

Sunt clasa a noua. :)


Titlul: Răspuns: qsort
Scris de: Adrian Craciun din Aprilie 12, 2011, 14:26:59
Daca nu scrii pe profil de unde vrei sa stiu :eyebrow:  ?
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


Titlul: Răspuns: qsort
Scris de: Simoiu Robert din Aprilie 12, 2011, 14:30:26
@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.


Titlul: Răspuns: qsort
Scris de: Sorin Rita din Aprilie 12, 2011, 14:37:16
Pai el vrea crescator dupa first si,in caz de egalitate, descrescator dupa second  :-'


Titlul: Răspuns: qsort
Scris de: Adrian Craciun din Aprilie 12, 2011, 14:38:53
@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  :) )


Titlul: Răspuns: qsort
Scris de: Simoiu Robert din Aprilie 12, 2011, 14:42:29
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 :P.


Titlul: Răspuns: qsort
Scris de: Sorin Rita din Aprilie 12, 2011, 14:43:57
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  :rotfl:


Titlul: Răspuns: qsort
Scris de: Adrian Craciun din Aprilie 12, 2011, 14:53:55
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 :ok:


Titlul: Răspuns: qsort
Scris de: Simoiu Robert din Aprilie 12, 2011, 15:09:15
Da, si faza cu crescator / descrescator era doar "un exemplu", eu am dat cazul general :P, pentru ca Sorin a pus cu cmp :).


Titlul: Răspuns: qsort
Scris de: Petru Dimitriu din Aprilie 12, 2011, 16:16:14
Trebuie sa declar un header, ceva? Ca vad ca nu imi compileaza.


Titlul: Răspuns: qsort
Scris de: Adrian Craciun din Aprilie 12, 2011, 16:18:24
Pune codul ca sa-ti zic ce trebuie sa mai pui (header #include<algorithm> pt. sort )


Titlul: Răspuns: qsort
Scris de: Sorin Rita din Aprilie 12, 2011, 16:25:10
si pune si

Cod:
  using namespace std;


Titlul: Răspuns: qsort
Scris de: Petru Dimitriu din Aprilie 12, 2011, 18:51:33
Multumesc. :)