QuickSort

[•Florian]

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. 

[•devilkind]

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.

[•Florian]

Mh...m-ai kam bagat in ceata  Ai putea sa-mi traduci putin scriind un pseudocod, sau ceva de genu asta? te rog...[ps: Doar dak ai timp ]

[•Marius]

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.

[•devilkind]

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.

[•Marius]

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

[•Florian]

Ok! Am inteles ambele surse! Va multumesc de ajutor! 

[•Prostu]

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.

[•Florian]

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.

[•stef2n]

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.

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.

[•Florian]

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?

[•devilkind]

e chiar asa greu ca in loc de a si b sa pui x si y.

[•Florian]

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 . 

[•stef2n]

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.

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

[•devilkind]

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.

[•Florian]

Dapz..da eroare...

[•Prostu]

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];
}

[•rEbyTer]

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
      }