Verständnissproblem bei qsort()

daishi

Ich will ein 2D Feld mittels qsort() sortieren.
Mein Programm sieht wie folgt aus:

int compare( const void *a, const void *b )
{
  int* z1=(int*) a;
  int* z2=(int*) b;

  if(z1[0]>z2[0]) return 1;
  if(z1[0]==z2[0])
  {
    if(z1[1]>z2[1]) return 1;
    if(z1[1]==z2[1]) return 0;
    if(z1[1]<z2[1]) return -1;
  }
  if(z1[0]<z2[0]) return -1;
  return 0;
}
int main(int argc, char* argv[])
{
  int feld[10][2]={{5,10},{5,11},{5,20},{3,12},{2,21},{1,13},{4,22},{6,23},{9,14},{0,24}};
  int i=0;
  int **feld2=new int*[10];
  for(i=0; i<10; i++)
  {  //kopieren des statischen in ein dynamisches feld
    feld2[i]=new int[2];
    feld2[i][0]=feld[i][0];
    feld2[i][1]=feld[i][1];
    cout<<feld2[i][0]<<" : "<<feld2[i][1]<<endl;
  }

  qsort(feld2,10,8,compare);
  for(i=0; i<10; i++)
  {
    cout<<feld2[i][0]<<" : "<<feld2[i][1]<<endl; //Zeigerfehler!!
  }
  return 0;
}

Wenn ich qsort mit dem statischen Feld aufrufe funktioniert es, nur bei dem dynamischen bekomme ich einen Zeigerverletzung.
Wo liegt da jetzt mein Denkfehler?

Jester

Kurze Zwischenfrage:

Warum verwendest Du nicht std::sort? Das ist einfacher zu benutzen und oft sogar schneller.

MfG Jester

daishi

Ok, danke werder es mal versuchen.

Es wäre trotzdem schön, wenn ich noch den Fehler im Programm finden würde.

Wenn du ein mehrdimensionales Array auf dem Stack anlegst, werden die Werte alle hintereinander in den Speicher geschrieben. Das bedeutet, dass, wenn du es als eindimensionales Array interpretierst, effektiv die Werte der Unter-Arrays direkt hintereinander stehen.

An deinem Beispiel:

int feld[10][2]={{5,10},{5,11},{5,20},{3,12},{2,21},{1,13},{4,22},{6,23},{9,14},{0,24}};

Wenn du das an qsort übergibst, wird es als eindimensionales Array verstanden, so dass es denselben Effekt wie

int feld[10][2]={5,10,5,11,5,20,3,12,2,21,1,13,4,22,6,23,9,14,0,24};

hat. Das wird vom C-Standard nicht vorgeschrieben, aber die meisten (wenn nicht alle) Betriebssysteme implementieren den Stack so, dass es funktioniert. Das bedeutet, dass es ein bisschen gefährlich ist das so zu machen, und dass du es nicht tun solltest, wenn dir an der Portabilität deines Codes etwas gelegen ist.

Das dynamisch angelegte Array dagegen ist ein Array von Zeigern. Wenn du es in ein eindimensionales Array umcastest, hast du immer noch ein Array von Zeigern, deren Inhalt qsort nicht abprüft und deswegen nicht sortiert. Wenn du das durch qsort jagst, kriegst du mit hoher Wahrscheinlichkeit ziemlichen Blödsinn und mit etwas niedrigerer Wahrscheinlichkeit Speicherlöcher. Übrigens solltest du dir angewöhnen, angeforderten Speicher auch wieder freizugeben (mit delete bzw. delete[]).

daishi

@0xdeadbeef
Danke für die Erklärung.