Alphabetisch sortieren



  • Ich habe eine Frage bezüglich dem folgenden Code:

    #include<stdio.h>
    #include<string.h>
    
    void main() {
       char s[5][20], t[20];
       int i, j;
       clrscr();
    
       printf("\nEnter any five strings : ");
       for (i = 0; i < 5; i++)
          scanf("%s", s[i]);
    
       for (i = 1; i < 5; i++) {
          for (j = 1; j < 5; j++) {
             if (strcmp(s[j - 1], s[j]) > 0) {
                strcpy(t, s[j - 1]);
                strcpy(s[j - 1], s[j]);
                strcpy(s[j], t);
             }
          }
       }
    
       printf("\nStrings in order are : ");
       for (i = 0; i < 5; i++)
          printf("\n%s", s[i]);
    
       getch();
    }
    

    Der Anfang ist klar, jedoch habe ich bei der zweiten und dritten for-Schleife überhaupt keinen Durchblick mehr. Könnt ihr mir etwas auf die Sprünge helfen?



  • Wenn ich den Code lese:

    if (strcmp(s[j - 1], s[j]) > 0) {
    

    Wenn der Wert der Integer Werte/Zahlen von String s[j-1] < s[j] größer ist (0 ist gleich):

    strcpy(t, s[j - 1])
    

    ;
    In "t" (temporary?) den String von S[j-1] kopieren.

    strcpy(s[j - 1], s[j]);
    

    Den String an S[j - 1] mit dem String auf S[j] überschreiben.

    strcpy(s[j], t);
    

    Den String an s[j] mit dem String aus "t" überschreiben (um eines nach hinten setzen).

    So würde ich den Code lesen.


  • Mod

    Das ist Bubblesort mit Zeichenketten. Was genau verstehst du da dran nicht?

    Die Zeilen 15 bis 18 bedeuten so viel wie:
    Falls Zeichenkette Nummer j-1 "größer" (im alphabetischen Sinne) ist als Zeichenkette Nummer j, dann:
    {
    Kopiere Zeichenkette Nummer j-1 in den temporären Wert t.
    Kopiere Zeichenkette Nummer j an die Stelle der Zeichenkette j-1.
    Kopiere die temporäre Zeichenkette t an die Stelle der Zeichenkette j.
    }

    PS: Das sortiert übrigens weder wirklich alphabetisch (weil strcmp auf Groß- und Kleinschreibung achtet) noch sollte Bubblesort jemals irgendwo eingesetzt werden, außer als mahnendes Beispiel, wie man möglichst nicht sortieren sollte.



  • SeppJ schrieb:

    Das ist Bubblesort mit Zeichenketten. Was genau verstehst du da dran nicht?

    Die Zeilen 15 bis 18 bedeuten so viel wie:
    Falls Zeichenkette Nummer j-1 "größer" (im alphabetischen Sinne) ist als Zeichenkette Nummer j, dann:
    {
    Kopiere Zeichenkette Nummer j-1 in den temporären Wert t.
    Kopiere Zeichenkette Nummer j an die Stelle der Zeichenkette j-1.
    Kopiere die temporäre Zeichenkette t an die Stelle der Zeichenkette j.
    }

    PS: Das sortiert übrigens weder wirklich alphabetisch (weil strcmp auf Groß- und Kleinschreibung achtet) noch sollte Bubblesort jemals irgendwo eingesetzt werden, außer als mahnendes Beispiel, wie man möglichst nicht sortieren sollte.

    Eine Recherche über Bubblesort und ein paar selbstgemachte Zeichnungen auf Papier haben mir geholfen das nun zu verstehen. Danke für den Begriff.

    Was sich mir jedoch noch nicht ganz erschließt ist, warum s[] als zweidimensionales Array initialisiert wird?

    Zudem; warum sollte man auf diese Art und Weise nicht mehr sortieren?



  • CrispyTurtleAlligator schrieb:

    Was sich mir jedoch noch nicht ganz erschließt ist, warum s[] als zweidimensionales Array initialisiert wird?

    Um Zeichenketten zu speichern, brauchst du ein 1D-Array von char.

    Zum sortieren bietet sich auch ein Array an. Sonnst wird das mit den Variablennamen ekelig 😉
    Du brauchst also ein Array für Zeichenketten.
    Das ergibt ein Array von Arrays von char: ein 2D-Array

    CrispyTurtleAlligator schrieb:

    Zudem; warum sollte man auf diese Art und Weise nicht mehr sortieren?

    Weil das Laufzeitverhalten ( https://de.wikipedia.org/wiki/Laufzeit_(Informatik) ) schlecht ist.
    Zudem gibt es mit qsort einen besseren Sortieralgorithmus in der C-Standardbibliothek.



  • DirkB schrieb:

    CrispyTurtleAlligator schrieb:

    Was sich mir jedoch noch nicht ganz erschließt ist, warum s[] als zweidimensionales Array initialisiert wird?

    Um Zeichenketten zu speichern, brauchst du ein 1D-Array von char.

    Zum sortieren bietet sich auch ein Array an. Sonnst wird das mit den Variablennamen ekelig 😉
    Du brauchst also ein Array für Zeichenketten.
    Das ergibt ein Array von Arrays von char: ein 2D-Array

    CrispyTurtleAlligator schrieb:

    Zudem; warum sollte man auf diese Art und Weise nicht mehr sortieren?

    Weil das Laufzeitverhalten ( https://de.wikipedia.org/wiki/Laufzeit_(Informatik) ) schlecht ist.
    Zudem gibt es mit qsort einen besseren Sortieralgorithmus in der C-Standardbibliothek.

    Genau hier liegt mein Verständnisproblem: Ich sehe zu keinem Zeit im Programm, dass dann darauf zugegriffen wird. Es ist dauernd nur von s[] und nicht von s[][] die Rede.

    Und damit wäre das "warum nicht" auch geklärt. Danke. 🙂



  • CrispyTurtleAlligator schrieb:

    Genau hier liegt mein Verständnisproblem: Ich sehe zu keinem Zeit im Programm, dass dann darauf zugegriffen wird. Es ist dauernd nur von s[] und nicht von s[][] die Rede.

    Weil den Vergleich und das Kopieren der Zeichen (das wäre dann s[][]) die Stringfunktionen strcmp und strcpy machen.



  • Wenn man wie hier tatsächlich ein Array von char-Arrays hat, dann gibt es auch die Kurzlösung mit qsort:

    int main() {
       char s[5][20], t[20];
       int i, j;
    
       printf("\nEnter any five strings : ");
       for (i = 0; i < 5; i++)
          scanf("%s", s[i]);
    
       qsort(s,5,20,strcmp);
    
       printf("\nStrings in order are : ");
       for (i = 0; i < 5; i++)
          printf("\n%s", s[i]);
    
       return 0;
    }
    

    http://ideone.com/SMJvuD



  • DirkB schrieb:

    CrispyTurtleAlligator schrieb:

    Genau hier liegt mein Verständnisproblem: Ich sehe zu keinem Zeit im Programm, dass dann darauf zugegriffen wird. Es ist dauernd nur von s[] und nicht von s[][] die Rede.

    Weil den Vergleich und das Kopieren der Zeichen (das wäre dann s[][]) die Stringfunktionen strcmp und strcpy machen.

    Immer noch nicht klar, warum das so ist, aber ich muss das wohl einfach so hinnehmen und akzeptieren.



  • Wutz schrieb:

    Wenn man wie hier tatsächlich ein Array von char-Arrays hat, dann gibt es auch die Kurzlösung mit qsort:

    int main() {
       char s[5][20], t[20];
       int i, j;
    
       printf("\nEnter any five strings : ");
       for (i = 0; i < 5; i++)
          scanf("%s", s[i]);
     
       qsort(s,5,20,strcmp);
     
       printf("\nStrings in order are : ");
       for (i = 0; i < 5; i++)
          printf("\n%s", s[i]);
     
       return 0;
    }
    

    http://ideone.com/SMJvuD

    Hier gibt mir Xcode folgende Warnung und Fehler aus:

    Xcode schrieb:

    Warnung: Implicit declaration of function 'qsort' is invalid in C99
    Error: Conflicting types for 'qsort'



  • qsort ist in stdlib.h deklariert.
    Den Header musst du auch mit einfügen.

    CrispyTurtleAlligator schrieb:

    Immer noch nicht klar, warum das so ist, aber ich muss das wohl einfach so hinnehmen und akzeptieren.

    Du könntest auch ein

    typedef char String19[20]; // Neuer Typ String19
    
    int main() {
       String19 s[5], t;
    

    Damit versteckst du das 1D-Array der Zeichenkette.



  • DirkB schrieb:

    qsort ist in stdlib.h deklariert.
    Den Header musst du auch mit einfügen.

    CrispyTurtleAlligator schrieb:

    Immer noch nicht klar, warum das so ist, aber ich muss das wohl einfach so hinnehmen und akzeptieren.

    Du könntest auch ein

    typedef char String19[20]; // Neuer Typ String19
    
    int main() {
       String19 s[5], t;
    

    Damit versteckst du das 1D-Array der Zeichenkette.

    Dein Code war der Folgende:

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int main() {
        char s[5][20], t[20];
        int i, j;
    
        printf("\nEnter any five strings : ");
        for (i = 0; i < 5; i++)
            scanf("%s", s[i]);
    
        qsort(s,5,20,strcmp);
    
        printf("\nStrings in order are : ");
        for (i = 0; i < 5; i++)
            printf("\n%s", s[i]);
    
        return 0; 
    }
    

    Dann ist die eine Fehlermeldung zwar weg, dafür kommen neue Fragen auf. Warum wird t und j initialisiert aber nicht genutzt? Ebenfalls erscheint folgende Warnung:

    Incompatible pointer types passing 'int (const char *, const char ) to parameter of type 'int ()(const void *, const void *)'

    Auch ist der Grund für das zweidimensionale Array immer noch nicht klar. Kann mir irgendjemand Schritt für Schritt erklären, warum das zweidimensionale Array nötig ist und ein eindimensionales Array nicht ausreicht?



  • CrispyTurtleAlligator schrieb:

    Auch ist der Grund für das zweidimensionale Array immer noch nicht klar. Kann mir irgendjemand Schritt für Schritt erklären, warum das zweidimensionale Array nötig ist und ein eindimensionales Array nicht ausreicht?

    'char' ist genau ein einzelnes Zeichen ('A' oder 'q' oder ...)

    Du willst aber nicht einzelne Zeichen haben, sondern du willst mit Wörter arbeiten(sortieren). Also brauchst du: 'char[]' um ein Wort darzustellen. D.h.
    'Wort' == 'char[]'.

    Was willst du machen? - Wörter sortieren!
    Also brauchst du eine Liste von Wörtern:
    Wort[]
    Nachdem Wort = char[] heißt das, du brauchst:
    char[][].

    Warum du kein [][] im Code siehst, liegt wie bereits erwähnt daran, dass das in der Bibliotheksfuntion gehandhabt wird.
    In dem Orginalcode steht:

    strcmp(s[j - 1], s[j])
    

    Die Funktion strcmp selber, macht dann in etwa folgendes:

    int strcmp(char[] a, char [] b) {
    // ...
    // fuer jedes Zeichen in den zwei Woertern:
    if (a[i] == b[i]) {
    // ...
    }
    

    Nachdem a der erste Parameter ist, also s[j-1], steht da effektiv:

    if (s[j-1][i] == s[j][i]) {
    

    Und damit hast du deine [][]. Die zwei Klammern sind nur auf verschiedene Teile des Programms aufgetrennt.

    Achja, dein 2D-Array sieht dann in etwa so aus:
    'H' | 'a' | 'u' | 's' | |
    'B' | 'a' | 'u' | 'm' | |
    'G' | 'a' | 'r' | 't' | 'e' | 'n'
    ...



  • Danke! Manchmal denke ich mir nur: Natürlich, da hätte ich auch selbst drauf kommen können. Bin ich aber nicht, trotz langer Überlegung. Aber dank deiner Erklärung habe ich es nun geschnallt. 😉


Log in to reply