Hilfe bei qsort

[Michael (Gast)]

Hallo,

ich benötige Hilfe bei qsort.

typedef struct
{
  u08 nr;
  char name[9];
} TEMP;
TEMP sortlist[100];

die Daten sind z.B. so belegt:

sortlist[0].nr=0;
sortlist[0].name={"zbc"};
sortlist[1].nr=1;
sortlist[1].name={"bcd"};
sortlist[2].nr=2;
sortlist[2].name={"aaa"};
sortlist[3].nr=3;
sortlist[3].name={"xa"};

nach der Sortierung sollte es so aussehen:

sortlist[0].nr=3;
sortlist[0].name={"zbc"};
sortlist[1].nr=1;
sortlist[1].name={"bcd"};
sortlist[2].nr=0;
sortlist[2].name={"aaa"};
sortlist[3].nr=2;
sortlist[3].name={"xa"};

jetzt muß man eine compare funktion schreiben und mit qsort aufrufen.
Ich habe schon einige Versuche hintermir und komme nicht mehr weiter:-(

[Karl H. (kbuchegg)]

Michael wrote:
>
> nach der Sortierung sollte es so aussehen:
>
> sortlist[0].nr=3;
> sortlist[0].name={"zbc"};
> sortlist[1].nr=1;
> sortlist[1].name={"bcd"};
> sortlist[2].nr=0;
> sortlist[2].name={"aaa"};
> sortlist[3].nr=2;
> sortlist[3].name={"xa"};

So sehr ich auch suche, aber dein Sortierkriterium erschliest
sich mir überhaupt nicht. Das ist weder nach name noch nach nr
sortiert. Wenn überhaupt, könnte man noch die Stringlänge als
absteigend sortiert betrachten. Aber da jetzt plötzlich die
Datensätze die vorher zusammengehörten (0 und zbc) auseinandergerissen
sind, würde ich mal schätzen:
Versuch das noch mal neu zu formulieren.

[Michael (Gast)]

Es sind 100 strings unsortiert im eeprom abgelegt.
um diese sortiert am Display anzuzeigen muß ich sortieren.
Vor der Ausgabe brauche ich eine Liste die mir die richtige Reihenfolge 
vorgibt um die Daten aus dem EEprom zu lesen.

[Uhu U. (uhu)]

Gehen wir mal davon aus, daß du nach name sortieren willst - aus deinen 
Postings geht das ja leider nicht klar hervor, dann sieht die 
Vergleichsroutine so aus:

int cmp(char *str1, char *str2) {
   return strcmp(str1, str2);
}

Du könntest also auch strcmp an qsort übergeben... Möglicherweise wirst 
du den Funktionspointer nach int (*)(void *, void *) casten müssen.

[Karl H. (kbuchegg)]

Michael wrote:
> Vor der Ausgabe brauche ich eine Liste die mir die richtige Reihenfolge
> vorgibt um die Daten aus dem EEprom zu lesen.

Alles klar. Du willst einen Index aufbauen und den Index so
umsortieren, dass die Indexverweise sortiert sind.

Wo ist das Problem?
Du definierst dir ein Array von char Pointern.
In dieses Array schreibst die die EEProm-String-Adressen hinein.

Mittels qsort wird dann dieses Hilfsarray sortiert, wobei die
Compare Funktion diesen Pointer auswertet und den String-
Vergleich (mit den Daten aus dem EEPRom) durchführt.
Compare muss zurück liefern:
   +1   wenn der erste String größer war als der zweite
   -1   wenn der erste String kleiner war als der zweite
    0   wenn die beiden Strings gleich sind.

Nach dem qsort hast du dann ein Array von character Pointern,
die du nur noch der Reihe nach durchgehen musst, um die Strings
in der richtigen Reihenfolge zu bekommen.

Jetzt mal ohne EEPROM, dafür direkt im Speicher:

Du hast eine Array mit den Strings:
  char Strings[4][] = { "abcd",
                        "defg",
                        "xc",
                        "1234",
                      };

dann gibt es weiters dein IndexArray.

char* Index[4];

das befüllst du mal mit Pointern in der richtigen Reihenfolge

  for( i = 0; i < 4; ++i )
    Index[i] = Strings[i];

Für den qsort brauchst du die Compare Funktion. Komplett
sieht das dann so aus:

char* Strings[4] = { "abcd",
                     "defg",
                     "xc",
                     "1234",
                   };

char* Index[4];

int Compare( const void* Arg1, const void* Arg2 )
{
  char* pString1 = *(char**) Arg1;
  char* pString2 = *(char**) Arg2;
  
  return strcmp( pString1, pString2 );
}

int main()
{
  int i;
  
  for( i = 0; i < 4; ++i )
    Index[i] = Strings[i];

  qsort( Index, 4, sizeof *Index, Compare );

  for( i = 0; i < 4; ++i )
    printf( "%s\n", Index[i] );

  return 0;
}

Wenn du nicht mit einem Pointer Index arbeiten möchtest, dann
würde das so aussehen:

char* Strings[4] = { "abcd",
                     "defg",
                     "xc",
                     "1234",
                   };

int Index[4];

int Compare( const void* Arg1, const void* Arg2 )
{
  int Index1 = * (int*) Arg1;
  int Index2 = * (int*) Arg2;
  
  return strcmp( Strings[Index1], Strings[Index2] );
}

int main()
{
  int i;
  
  for( i = 0; i < 4; ++i )
    Index[i] = i;

  qsort( Index, 4, sizeof *Index, Compare );

  for( i = 0; i < 4; ++i )
    printf( "%s\n", Strings[Index[i]] );

  return 0;
}

Entscheidend ist, dass du dir in der Compare Funktion den
übergebenen Pointer wieder auf den richtigen Datentyp
zurückcasten musst. Die Compare Funktion bekommt immer
einen Pointer auf den Datentyp, aus dem das Array besteht.
Besteht das Array aus int, so kriegt die Compare Funktion
jeweils einen Pointer auf int. Besteht dein Array aus double,
so kriegt die Compare Funktion einen Pointer auf double.
Besteht das Array aus char*, so kriegt die Compare Funktion
einen Pointer auf char*. Besteht das Array aus struct irgendwas,
so kriegt die Compare Funktion Pointer auf struct irgendwas.
Der jeweilige Pointer muss wieder in den richtigen Datentyp
zurückgewandelt werden und dann dereferenziert werden um
an die eigentlichen zu sortierenden Daten heranzukommen.
Mit denen machst du dann an Vergleichen was auch immer
notwendig ist, um die Sortierreihenfolge zu bestimmen.

[Michael (Gast)]

WOW vielen Dank für Deine Ausführung Karl Heinz.
Das werde ich mal durcharbeiten und so versuchen, deine Hilfe hat noch 
immer zum Ziel geführt.
Besten Dank

[Michael (Gast)]

Irgendwo habe ich doch noch was falsch, das Ergebnis stimmt noch nicht.

So habe ich es jetzt eingefügt:

char* Namen[100];

int Compare( const void* Arg1, const void* Arg2 )
{
  int Index1 = * (int*) Arg1;
  int Index2 = * (int*) Arg2;
  
  return strcmp( Namen[Index1], Namen[Index2] );
}


 //Mit Namen aus dem EEprom laden number = Anzahl der Einträge
 for(x=0;x<number;x++)
 {
  readwp(x+1);
  strncpy(Namen[x],WayPoint.name,8);
 }

for( i = 0; i < number; ++i )Index[i] = i;

  qsort( Index, number, sizeof *Index, Compare );


//Daten sortiert ausgeben
readwp(Index[pos]);

[Karl H. (kbuchegg)]

Michael wrote:
> Irgendwo habe ich doch noch was falsch, das Ergebnis stimmt noch nicht.
>
> So habe ich es jetzt eingefügt:
>

> 
> char* Namen[100];
> 
> int Compare( const void* Arg1, const void* Arg2 )
> {
>   int Index1 = * (int*) Arg1;
>   int Index2 = * (int*) Arg2;
> 
>   return strcmp( Namen[Index1], Namen[Index2] );
> }
> 
> 
>  //Mit Namen aus dem EEprom laden number = Anzahl der Einträge
>  for(x=0;x<number;x++)
>  {
>   readwp(x+1);
>   strncpy(Namen[x],WayPoint.name,8);
>

Aeh. Nein, das geht so nicht. (Mal ganz davon abgesehen,
dass es sich immer um den gleichen Waypoint Namen handelt)

Hinter Namen verbirgt sich ja keine Speicherfläche, in der
du einen String speichern könntest. So wie du das hast, kann
in Namen lediglich ein Pointer abgespeichert sein. Zb. Die
Speicheradresse des Strings im EEPROM (Wink, Wink).

Mit anderen Worten: Kopiere die Strings nicht vom EEPROM
in den SRAM Speicher:
1) Braucht das ziemlich viel Platz im SRAM
2) denke ich, dass das in Summe (*) auch nicht schneller ist,
   als wie wenn du die ganze Vergleichsfunktion auf Daten im
   EEPROM ausführen lässt.
   Dazu kannst du dann aber nicht strcpy benutzen, da strcpy
   die Strings im SRAM erwartet und nicht im EEPROM.
3) Wenn deine Waypoint namen sowieso immer nur 8 Zeichen lang
   sein können, kannst du ja auch die Indexmethode mit int
   (oder unsigned char) anstelle von char Pointern benutzen.
   Du kannst ja aus der Startadresse der Waypoints und einer
   Indexnummer ganz leicht die Speicheradresse (im EEPROM)
   berechnen, an der der Name des Waypoints gespeichert ist.
   Das benutzt du dann in der Compare Funktion um die Adresse
   im EEPROM zu bestimmen an der der erste zu vergleichende
   Namen gespeichert ist. Selbiges für den zweiten Namen.
   Diese beiden werden dann miteinander verglichen. Aber nicht
   mit strcpy, sondern da wirst du dir eine eigene Funktion
   machen müssen, die das kann und ein Ergebnis in Analogie
   zu strcpy liefert.

(*) Mit in Summe meine ich: Den kompletten Vorgang des Kopierens
  aller Strings vom EEPROM in den SRAM. Die Compare Funktion auf
  Daten im EEPROM ist zwar langsamer als wie wenn die Daten im
  SRAM liegen würden. Allerdings wird das dadurch aufgewogen,
  dass die Umkopieraktion ja auch Zeit braucht.

[Michael (Gast)]

hab ich einigermasen verstanden.
bei readwp() wird ein ganzer Datensatz (struct) gelesen, somit steht in 
Waypoint.name immer ein anderer Namen.
Die Speicheradresse berechnen ist leicht.
Startadresse = FIRSTWP = 0x40
LENGTHOFWP = 0x13

[Karl H. (kbuchegg)]

Michael wrote:
> hab ich einigermasen verstanden.
> bei readwp() wird ein ganzer Datensatz (struct) gelesen, somit steht in
> Waypoint.name immer ein anderer Namen.

Spaetestens jetzt rächen sich die globalen Variablen.
Es wäre besser, wenn readwp ganz einfach eine struct returnieren
würde, anstatt eine globale Variable befüllen. Sowas ist immer
schlecht.

Das ganze mit einem byte Array für die Indizes (Dein Maximum
liegt ja bei 100, und das passt locker in ein Byte).

Dann könntest du in der Compare Funktion schreiben

int Compare( const void* Arg1, const void* Arg2 )
{
  uint8_t Index1 = * (uint8_t*) Arg1;
  uint8_t Index2 = * (uint8_t*) Arg2;
  
  struct Wayp Point1 = readwp( Index1 );
  struct Wayp Point2 = readwp( Index2 );
  
  return strcmp( Point1.name, Point2.Name );
}

int main()
{
  uint8_t SortIndizes[100];
  uint8_t i;
  struct Wayp ThePoint;

  for( i = 0; i < number; ++i )
    SortIndizes[i] = i;

  qsort( SortIndizes, number, sizeof *SortIndizes, Compare );

  for( i = 0; i < number; ++i ) {
    ThePoint = readwp( SortIndizes[i] );    
    printf( "%s\n", ThePoint.name );
  }
}

Merke: Die richtige Wahl dessen, was eine Funktion macht und wie
sie die Ergebnisse präsentiert, kann einen riesen Unterschied
ausmachen, welche Möglichkeiten du in einem Programm hast.

struct Wayp readwp( uint8_t Nr )
{
  struct Wayp tmp;

  // mach was auch immer zu tun ist, um den Waypoint mit der
  // Nummer Nr zu besorgen und die gelesenen Daten in tmp
  // zu speichern

  return tmp;
}

[Michael (Gast)]

typedef struct
{
 float   laenge,
         breite;
 s16     alti;
 char name[9];
} WAYPOINT;//19 Bytes

WAYPOINT WayPoint;

//die Funktion readwp(u08 pos)
//liest die struct WayPoint an pos aus dem EEprom.
//Wenn pos=5 wird der 5te WayPoint ausgelesen.

//Die Comparefunktion sieht so aus: 
int Compare( const void* Arg1, const void* Arg2 )
{
  u08 Index1 = * (u08*) Arg1;
  u08 Index2 = * (u08*) Arg2;
  
  readwp( Index1 );
  WAYPOINT Point1 = WayPoint;
  readwp( Index2 );
  WAYPOINT Point2 = WayPoint;
  
  return strcmp( Point1.name, Point2.name );
}

u08 i,SortIndizes[100];
 
 for( i = 0; i < number; ++i )SortIndizes[i] = i;
 qsort( SortIndizes, number, sizeof *SortIndizes, Compare );

//Auslesen der Wegpunkte in sortierter Reihenfolge:
for( i = 0; i < number; ++i )
{
 readwp( SortIndizes[i] );  
 printf( "%s\n", WayPoint.name );
}