infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Florian Marcu din Iunie 04, 2007, 16:47:06



Titlul: QuickSort
Scris de: Florian Marcu din Iunie 04, 2007, 16:47:06
Cu totii stim ca exista functia predefinita qsort! Eu am invatat-o de curand!

Cod:

int intcmp(const void*a, const void*b)
     {
      return *(int*)a-*(int*b);
      }
int main()
     {
     //citim vectorul a[].
       
      qsort(a,n,sizeof(a[0]),intcmp);
     
      //si vectorul e sortat...
       
      return 0;
      }

Am inteles-o intr-o oarecare masura... Problema mea este cum fac pentru a sorta dupa doua sau mai multe criterii, dak se poate, of course. De asemeni, m-ar mai interesa cum fac, folosind aceasta forma scurta, pentru a interskimba si alte elemnte pe langa elementele vectorului ( a[] in cazul de fata). Adik de exemplu vreau sa retin un vector de indici, si pt fiecare interskimbare din qsort sa interschimb si indicii. Deci, dak ar putea cineva raspunde la aceste 2 intrebari, mi-ar fi de mare ajutor.  :thumbup:


Titlul: Răspuns: QuickSort
Scris de: Savin Tiberiu din Iunie 04, 2007, 18:00:26
pai eu folosesc o chestie care merge cam intotdeauna. cand vreau sa sortez dupa mai multe criterii initializez un vector ord cu permutarea identica (1 2 3 4 .. n) iar apelez functia qsort ptr acest vector iar in functia de comparare *(int *) a va fi un indice catre vectorul meu. Avand sortati indici poti sa faci o parcurgere simpla ca sa iti sortezi vectorul.


Titlul: Răspuns: QuickSort
Scris de: Florian Marcu din Iunie 04, 2007, 18:15:17
Mh...m-ai kam bagat in ceata  :oops: Ai putea sa-mi traduci putin scriind un pseudocod, sau ceva de genu asta? te rog...[ps: Doar dak ai timp ]


Titlul: Răspuns: QuickSort
Scris de: Marius Stroe din Iunie 04, 2007, 21:23:00
Daca retii intr-o structura toate informatiile de care ai nevoie, atunci in functia cmp() ai acces la ce doresti. Cand se interschimba elemente vectorului intre ele, se interschimba toate informatiile.


Titlul: Răspuns: QuickSort
Scris de: Savin Tiberiu din Iunie 04, 2007, 21:41:55
nu ma refeream tocmai la ideea asta ptr ca lucrul cu structuri e destul de lent, desi cred ca la urma urmei tot cam acolo se ajunge cu ambele metode. Uite un mic pseudocod in care sortez un sir de puncte in dupa coordonata x iar in caz de egalitate dupa y.

Cod:

struct punct{long int x, y} a[100],b[100];

long int ind[NMAX];

//citesti punctele bla bla bla bla

int cmp(const void *a, const void *b)
{
long int x = * (long int *) a, y = * (long int *) b;
if (a[x].x==a[y].x) return a[x].y - a[x].y;
return a[x].x - a[y].x;
}

void sortare()
{
for (i=1;i<=n;i++)
    ord[i]=i;

qsort(ord, n+1, sizeof(long int), cmp);

for (i=1;i<=n;i++)
   b[i]=a[ord[i]];
}
   
in ord retin indici dupa sortare. Dezavantajul acestei metode este nevoia unui vector auxiliar (vectorul b in cazul meu). Sper ca ai inteles ce am vrut eu sa zic.

PS: nu sunt sigur ca acel cod de mai sus nu va avea mici greseli de sintaxa, e scris asa pur si simplu dar tind sa cred ca e corect.




Titlul: Răspuns: QuickSort
Scris de: Marius Stroe din Iunie 04, 2007, 22:27:22
Cod:
...
#include <algorithm>
using namespace std;

#define MAX_N  10000
...
struct entry {
    double x, y;   /* coordonatele */
    int p;              /* indice */
} E[MAX_N];
...

void read_in(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) {
         scanf("%lf %lf", &E[i].x, &E[i].y);
         E[i].p = i;   
    }
}

int mycmp(entry a, entry b) {
    if (a.x != b.x)   
        return a.x < b.x;
    else
        return a.y < b.y;
}
   

int main(void) {
    read_in();
    sort(E, E + n, mycmp);
    return 0;
}

E un program inutil, dar am vrut sa vezi cum functioneaza functia sort() din headerul algorithm.h.
Cum a spus devilkind e mai rapid, fireste, pentru ca interschimba doar sizeof(int) [indicele], pe cand in cazul meu se muta date de dimensiune sizeof(entry).


Titlul: Răspuns: QuickSort
Scris de: Florian Marcu din Iunie 05, 2007, 07:49:23
Ok! Am inteles ambele surse! Va multumesc de ajutor!  :banana:


Titlul: Răspuns: QuickSort
Scris de: Stefan-Alexandru Filip din Iunie 05, 2007, 08:11:12
Citat
E un program inutil, dar am vrut sa vezi cum functioneaza functia sort() din headerul algorithm.h
O mica scapare, headerul se numeste algorithm simplu, iar numele headerului folosit pentru backward compatibility este algo.h (acesta teoretic nu ar trebui inclus niciodata). In standardul C++ headerele predefinite au scapat de extensia .h.


Titlul: Răspuns: QuickSort
Scris de: Florian Marcu din Iunie 05, 2007, 15:39:36

PS: nu sunt sigur ca acel cod de mai sus nu va avea mici greseli de sintaxa, e scris asa pur si simplu dar tind sa cred ca e corect.


S-ar putea sa dea eroare din cauza ca ai declarat global vectorul a[], iar in functia de comparare ai redeclarat a[]-ul ca fiind const void*a [parametrul]. Insa nu are nicio importanta. :thumbup:


Titlul: Răspuns: QuickSort
Scris de: Stefan Istrate din Iunie 05, 2007, 15:49:19
S-ar putea sa dea eroare din cauza ca ai declarat global vectorul a[], iar in functia de comparare ai redeclarat a[]-ul ca fiind const void*a [parametrul]. Insa nu are nicio importanta. :thumbup:
O astfel de eroare nu are cum sa dea. Poti declara variabile la nivel global, iar apoi sa le declari la nivel local cu acelasi nume. Nu e absolut nici o problema din punctul asta de vedere. Compilatorul va sti sa le diferentieze.


Titlul: Răspuns: QuickSort
Scris de: Florian Marcu din Iunie 05, 2007, 16:34:36
Mh...pai..compilatorul nu le transforma pe toate in variabile pt functia cmp? Adik in acea functie este folosita variabila "a" atat ca vector global, cat si k parametru. Odata declarat "a" drept parametru, se "pierde" variabila globala "a" pana cand este finalizata executarea functiei, nu?  Nu da eroare pt asa ceva, intrucat "a" este declarat const void , iar functia foloseste si "a"-ul care este vectorul global?


Titlul: Răspuns: QuickSort
Scris de: Savin Tiberiu din Iunie 05, 2007, 16:54:36
e chiar asa greu ca in loc de a si b sa pui x si y.


Titlul: Răspuns: QuickSort
Scris de: Florian Marcu din Iunie 05, 2007, 16:59:36
Nupz..Nu e asta o problema... Dar daca as scrie asa ceva in rhide cu singuranta ar da eroare... Deci nu am nimik cu codul tau, ci doar am vrut sa-l corectez pe stef2n .  :thumbup:


Titlul: Răspuns: QuickSort
Scris de: Stefan Istrate din Iunie 05, 2007, 17:29:59
Nupz..Nu e asta o problema... Dar daca as scrie asa ceva in rhide cu singuranta ar da eroare... Deci nu am nimik cu codul tau, ci doar am vrut sa-l corectez pe stef2n. :thumbup:
Intr-un program pot fi declarate mai multe variabile cu acelasi nume, dar nu la acelasi nivel. Prioritatea cea mai mare o au variabilele locale, iar cea mai mica o au cele globale. Un program de forma
Cod:
int x=0;

int main()
{
double x=1.23;

for(int i=0;i<100;i++)
   {
    char x='a';
   }

return 0;
}
este corect si compileaza sub gcc (si normal ca si sub rhide).
Pot exista si functii cu acelasi nume, dar ele trebuie sa difere prin numarul parametrilor sau prin tipul acestora. Compilatorul e o chestie desteapta si stie sa faca diferenta in astfel de situatii :thumbup:


Titlul: Răspuns: QuickSort
Scris de: Savin Tiberiu din Iunie 06, 2007, 08:12:35
stefan el de fapt se referea la alt caz.

ceva de genu
Cod:
long int a[100];

int cmp(const void *a, const void *b)
{
return a[ * (long int *) a ] - a[ * (long int *) b];
}

in acest caz s-ar putea sa dea eroare nu sunt sigur, e posibil ca gcc sa isi dea seama in functie de tipul de date la care te referi dar nush ce sa zic akuma, oricum e bine sa eviti astfel de lucruri.


Titlul: Răspuns: QuickSort
Scris de: Florian Marcu din Iunie 06, 2007, 08:22:46
Dapz..da eroare... :thumbup:


Titlul: Răspuns: QuickSort
Scris de: Stefan-Alexandru Filip din Iunie 06, 2007, 08:48:27
Ca sa nu dea eroare faci asa
Cod:
long int a[100];

int cmp(const void *a, const void *b)
{
return ::a[ * (long int *) a ] - ::a[ * (long int *) b];
}


Titlul: Răspuns: QuickSort
Scris de: Herpesius din Martie 16, 2008, 17:41:28
In C++ este definit un operator de rezolutie ( :: ), care permite accesul la un identificator cu domeniu fisier, dintr-un bloc în care acesta nu este vizibil, datorita unei alte declaratii.
Exemplu
Cod: (http://www.timsoft.ro/aux/module/modul1-plus.html)
      int n=1;
      void main() {
          int n=2;
          afiseaza(n); // afiseaza 2, valoarea variabilei locale n
          afiseaza(::n); // afiseaza 1,valoarea variabilei globale n
      }