Arrayeinträge sortieren



  • hi,
    ich finde im Netz leider nur Dürftiges (vieles leider nur auf Englisch) über das Sortieren eines von mir bestimmten Arrays.
    Ich habe ein Array mit dem Namen ziel. In diesem sind nur Integereinträge. und es hat folgende Einträge in dieser Reihenfolge:
    0,0,0,0,0,32,12,32,14,0,12,40
    dieses möchte ich sortiert haben in:
    0,0,0,0,0,0,12,12,14,32,32,40
    jedoch, wenn möglich, dass die Positionen sich gemerkt werden, villeicht sogar in ein weiteres Array geschrieben werden. Also hier Positionen:
    1,2,3,4,5,10,7,11,9,6,7,12
    wie ist dieses möglich?Wie führe ich den Quicksort (wird wohl der beste sein) von meinem Array 'ziel' durch?
    Kann mir da vielleicht jemand weiterhelfen?



  • du definierst einen Typ für dein Problem

    typedef struct
    {
      int key,val;
    } Eintrag;
    

    und arbeitest dann mit einem Array dieses Typs und nicht mit einem Array von ints.
    Dabei musst du dann, spätestens aber vor dem Sortieren (danach natürlich nicht mehr) die keys füllen.

    Eintrag liste[] = { {0,33}, {1,22}, {2,11}, ... };
    ...
    int cmp(const void *a,const void *b)
    {
      return ((Eintrag*)a)->val - ((Eintrag*)b)->val;
    }
    ...
    qsort( liste, zahldeinereintraegederliste, sizeof*liste, cmp );
    


  • ok,
    muss ich dabei vorher die Positionen bestimmen?
    ICh lese die Werte aus einer Datei ein und packe sie in ein Array.
    Sollte ich sie deiner Meinung nach vor dem ins Array packen sortieren? Das Problem ist, dass ich die Position des Einlesens brauche...

    Dein

    Eintrag liste[] = { {0,33}, {1,22}, {2,11}, ... };
    

    Weswegen nimmt du dort solche Zahlen? 33, 22, 11...
    Und vorher bei der Typdefinierung, wofür steht das Wort Eintrag?
    Gibt es dazu vielleicht ein Beispiel?



  • Deine Fragen lassen darauf schließen, dass du absoluter Anfänger bist.
    Mögen sich andere damit befassen, dir die C Grundlagen beizubringen.



  • Wutz schrieb:

    int cmp(const void *a,const void *b)
    {
      return ((Eintrag*)a)->val - ((Eintrag*)b)->val;
    }
    

    Achtung, Integerüberlauf!



  • ist es denn möglich, dass mit for Schleifen zu lösen?`

    for(m = 0; m < 12; m++) {
    for(x = 0; x < 12; x++) {
    if(zielPiRi[m] <= zielPiRi[m+x])
    {
    printf("test 1: %d\n", zielPiRi[m]);
    }
    		else 
    			printf("zum test: %d\n", zielPiRi[m+x]);
    }
    }
    

    Das haut mich leider um...
    Kann ich das 12 stellige Array anders sortieren?
    Bin Anfänger und kann nur die simpelsten Sachen.
    Vielleicht 12 forSchleifen???



  • Butterbrot23 schrieb:

    Kann ich das 12 stellige Array anders sortieren?

    Aber sicher:

    #include <stdio.h>
    #include <stdlib.h>
    
    /* zwei int's ueber Zeiger vergleichen */
    int
    compare_int(void const *a, void const *b)
    {
       int const m = *((int const *)a), n = *((int const *)b);
       if (m > n) return 1;
       else if (n > m) return -1;
       else return 0;
    }
    
    /* ein int-Array anzeigen */
    void
    show_ints(int *array, size_t size)
    {
       putchar('{');
       for (int i = 0; i < size; i++)
          printf(i + 1 < size ? "%d, " : "%d", array[i]);
       fputs("}\n", stdout);
    }
    
    int
    main(void)
    {
       /* dein Array */
       int zielPiRi[] = {0,0,0,0,0,32,12,32,14,0,12,40};
       /* die Groesse des Arrays */
       size_t size = sizeof zielPiRi / sizeof *zielPiRi);
    
       /* anzeigen */
       show_ints(zielPiRi, size);
    
       /* sortieren und nochmals anzeigen */
       qsort(zielPiRi, size, sizeof *zielPiRi, compare_int);
       show_ints(zielPiRi, size);
    }
    

    Das ist einfacher, als die Sortierfunktion selbst zu schreiben, und wahrscheinlich besser. Aber so verlierst du die ursprünglichen Positionen. Den ursprünglichen Zustand in einem anderen Array konservieren und dort die Positionen suchen geht auch nicht, weil manche Zahlen mehrfach vorkommen. Deshalb ist es wohl am schlausten, ein Array zum Sortieren zu verwenden, das in jedem Element auch seine Ursprungs-Position speichert (siehe Wutz).
    🙂



  • danke,
    ja die Positionen sind wichtig.
    Verstehe aber diese Zahlen 33, 22, 11 bei Wutz nicht.
    Ich denke die vorangegangenen Zahlen geben die Position an, richtig?
    Die Sache ist eben, dass ich die Zahlen vorher aus einer Datei einlese, und ich lese einige Dateien aus, da müsste ich jedes mal den Code ändern, sobald ich eine Datei auslese...
    Also einfacher geht das alles nicht?
    Im Internet gibt es leider nichts vernünftiges als Beispiele.



  • Butterbrot23 schrieb:

    Also einfacher geht das alles nicht?

    Also schwer ist die Sache doch wirklich nicht. Man ruft qsort und liefert dieser Funktion als letzten Parameter eine Vergleichsfunktion. Die Zahlen 33, 22, 11 sind von Wutz "willkürlich" gewählt, wichtig war nur, dass sie absteigend verlaufen, damit das Sortieren auch einen Effekt hat.
    Warum du jedes Mal den Code ändern müsstest, wenn du eine neue Datei einliest, verstehe ich auch nicht so richtig 😕 .
    Wie sind diese Dateien denn aufgebaut?
    Edit: Wenn dir Englisch so viele Probleme bereitet, dann solltest du schleunigst etwas daran tun!



  • Butterbrot23 schrieb:

    Die Sache ist eben, dass ich die Zahlen vorher aus einer Datei einlese, und ich lese einige Dateien aus, da müsste ich jedes mal den Code ändern, sobald ich eine Datei auslese...

    Wenn du die Zahlen in die eine Datenstruktur einlesen kannst, warum dann nicht auch in eine andere? Du kannst auch zuerst in die eine Datenstrukur lesen und dann in die andere umwandeln.
    🙂



  • ok,
    danke bislang für eure Hilfe, habe versucht den quicksort wie auf der Seite im Beispiel einzubinden.
    Ich habe die Funktion

    int n;
      qsort (values, 6, sizeof(int), compare);
      for (n=0; n<6; n++)
         printf ("%d ",values[n]);
    

    in meine
    int main(int argc, char* argv[]) {...} Funktion eingebunden.
    Dahinter die

    int compare (const void * a, const void * b)
    {
      return ( *(int*)a - *(int*)b );
    }
    

    Wenn ich dieses kompiliere, so beschwert er sich:

    1>.....cpp(151) : error C2065: 'compare': nichtdeklarierter Bezeichner
    1>.....cpp(151) : warning C4047: 'Funktion': Anzahl der Dereferenzierungen bei 'int (__cdecl *)(const void *,const void *)' und 'int' unterschiedlich
    1>.....cpp(151) : warning C4024: 'qsort': Unterschiedliche Typen für formalen und übergebenen Parameter 4
    1>.....cpp(170) : error C2365: "compare": Erneute Definition; vorherige Definition war "Datenvariable".

    Liegt es daran, dass ich nur die Express Version benutze??
    Oder worin liegt der Fehler?





  • DANKE!



  • Butterbrot23 schrieb:

    Liegt es daran, dass ich nur die Express Version benutze??

    Express Version? Wovon??
    🙂



  • Butterbrot23 schrieb:

    int compare (const void * a, const void * b)
    {
      return ( *(int*)a - *(int*)b );
    }
    

    Da stimmt was nicht:

    #include <stdio.h>
    #include <limits.h>
    
    int compare (const void * a, const void * b)
    {
       return ( *(int*)a - *(int*)b );
    }
    
    int
    main(void)
    {
       int a = INT_MAX;
       int b = -10;
       printf("%d", compare(&a, &b));
    }
    

    Gibt eine negative Zahl aus, obwohl a grösser als b ist, das Ergebnis also positiv sein sollte. Ist das Absicht?
    🙂



  • Wutz schrieb:

    du definierst einen Typ für dein Problem

    typedef struct
    {
      int key,val;
    } Eintrag;
    

    und arbeitest dann mit einem Array dieses Typs und nicht mit einem Array von ints.
    Dabei musst du dann, spätestens aber vor dem Sortieren (danach natürlich nicht mehr) die keys füllen.

    Eintrag liste[] = { {0,33}, {1,22}, {2,11}, ... };
    ...
    int cmp(const void *a,const void *b)
    {
      return ((Eintrag*)a)->val - ((Eintrag*)b)->val;
    }
    ...
    qsort( liste, zahldeinereintraegederliste, sizeof*liste, cmp );
    

    kann man dieses irgendwo als Beispiel sehen?
    Vorhin bei dem leichteren Beispiel mit dem Sortieren hattet ihr auch eine Seite, auf welcher ein solches Beispiel war.
    Denn ich habe Probleme dieses in mein Programm reinzuschreiben.
    Vor allem die Typdefinierung zu Beginn.



  • Butterbrot23 schrieb:

    kann man dieses irgendwo als Beispiel sehen?

    Am besten gar nicht, das ist verbuggt, wie schon von Security Bulletin bemerkt und von mir belegt. Solange du solche schweren Fehler nicht ernst nimmst, kann man dir leider nur schwer helfen.
    🙂



  • hmmm ok.
    Wie könnte ich es denn lösen?
    Ich werte Daten aus, diese sortiere ich und möchte weiterhin die Positionen der Einlesung vor dem Sortieren wissen.
    Habe bislang es in ein Array geschrieben, und wollte es vom Array aus machen, aber anscheinden ist das schwierig...Hat denn keiner eine Idee?
    Vielleicht etwas mit forSchleifen??? 🙂



  • Butterbrot23 schrieb:

    Wie könnte ich es denn lösen?

    Indem du ein Array von Strukturen verwendest, wie von Wutz beschrieben. Ich weiss nicht, wie du deine Daten einliest, deshalb zeige ich dir, wie man ein solches Array aus deinem bestehenden Array erzeugt:

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct
    {
       int key, val;
    }
    entry;
    
    /* zwei entries ueber Zeiger vergleichen */
    int
    compare_entry(void const *a, void const *b)
    {
       int const m = ((entry const *)a)->val;
       int const n = ((entry const *)b)->val;
       if (m > n) return 1;
       else if (n > m) return -1;
       else return 0;
    }
    
    int main(void)
    {
       int zielPiRi[] = {0,0,0,0,0,32,12,32,14,0,12,40};
       entry array[12];  /* oder mit malloc() anfordern */
       size_t const size = sizeof zielPiRi / sizeof *zielPiRi;
    
       /* 'array' mit den richtigen Indizes und Werten fuellen */
       for (int i = 0; i < size; i++)
       {
          array[i].key = i;
          array[i].val = zielPiRi[i];
       }
    
       /* 'array' sortieren */
       qsort(array, size, sizeof (entry), compare_entry);
    
       /* nachsehen, was passiert ist */
       for (int i = 0; i < size; i++)
          printf("%d war vorher an Platz %d\n", array[i].val, array[i].key);
    }
    

    Nach dem Sortieren zeigt sich der Vorteil dieser Vorgehensweise: dass wir uns den ursprünglichen Index der Elemente im 'key'-Member der Struktur gemerkt haben.
    🙂

    Edit: size ist jetzt ein size_t statt ein int .



  • danke erstmal,
    leider beschwert er sich beim Kompilieren:
    ...cpp(138) : error C2065: 'compare_entry': nichtdeklarierter Bezeichner
    ...cpp(206) : error C2365: "compare_entry": Erneute Definition; vorherige Definition war "Datenvariable".

    Wie bekomme ich diese Fehler weg?


Anmelden zum Antworten