Selection Sort (Array)



  • Hi Leute, wir haben unlängst mit C++ angefangen und nun gibt es folgende Aufgabe:

    Gegeben ist ein Array a der Größe size mit paarweise verschiedenen
    Elementen aus einem total geordneten Universum.
    Wir sollen nun ein Programm schreiben, welches zuerst das größte Element aus a findet
    und es mit dem letzten Element aus a vertauscht. Das restliche Array soll dann
    rekursiv sortiert werden. Die Funktion selection sort hat folgende Signatur:

    void selectsort(int a[], int size)

    Vorab erstmal meine Frage:
    Da steht ja das Array a hat die Größe size mit paarweise
    verschiedenen Elementen. Heißt das, dass der Benutzer aufgefordert wird eine Zahl
    einzugeben, welche dann der Anzahl der Elementenpaare im Array entspricht?
    Also wenn der Nutzer z.B. 10 eingibt, dann hat das Array 20 Elemente?
    Nur muss ich doch vorab angeben die größe des Arrays definieren oder?

    Lassen wir mal kurz das Finden des größten Elementes aus dem Array ausser Acht.
    Dann würde ich so anfangen:

    int main (void)
    {
        int a[16]; // hier muss ich doch schon angeben wie groß das Array sein soll oder?
        cout << "Gib die Anzahl der paarweise verschiedenen Elemente des Arrays an: ";
        cin >> size;
    }
    

    Ich danke euch schon mal für eure Unterstützung!



  • Paarweise verschieden heißt nur, daß keine 2 Elemente gleich sind.

    Woher die Größe des Arrays kommt, ist der Funktion völlig egal (d.h. ob als Konstante oder aber zur Laufzeit).
    Am besten also ersteinmal folgendes benutzen:

    const int size = 10;
    int a[size];
    
    // array füllen
    
    selectsort(a, size);
    

    Die Größe muß explizit bei der Funktion angegeben werden, weil int a[] nichts anderes als int a* entspricht, d.h. nur die Anfangsadresse des Arrays übergeben wird.



  • Zu deiner Frage, ob erstmal der Benutzer etwas eingeben soll: Du schreibst doch selbst "Gegeben ist ein Array a der Größe size mit paarweise verschiedenen
    Elementen aus einem total geordneten Universum.". Dieses Array ist also gegeben. Eine Benutzereingabe ist zur Lösung dieser Aufgabe nicht nötig.

    Umgekehrt: ich würde die empfehlen, ein paar verschiedene Beispielarrays zu machen, mit denen du dann deine zu schreibende Funktion testen kannst.

    Also z.B. so:

    void selectsort(int a[], int size) {
      ...
    }
    
    int main(/* in C++ wird im Gegensatz zu C KEIN void benötigt */) {
      int testarray[] = { 8, 42, 23, 17 }; // Länge kann automatisch ermittelt werden
      selectsort(testarray, sizeof(testarray) / sizeof(testarray[0]));
      std::cout << "Array sortiert:\n";
      for (const auto &val : testarray)
        std::cout << val << " ";
      std::cout << "\n";
    }
    

    Es sei noch angemerkt, dass die Paramterübergabe mit einem Pointer und einer Länge sehr nach C aussieht - in modernem C++ würde man das anders lösen. Ist für dein Problem aber jetzt eigentlich erstmal egal.



  • Hey Leute! Danke euch, das Programm läuft jedoch musste ich in meine Signatur noch was dazutun, damit die Funktion rekursiv ist. Sie sieht jetzt so aus:

    void selectsort ( int a[], int size, int index = 0 )
    

    Iterativ hat es ohne index = 0 geklappt.



  • Wozu benötigst du diesen zusätzlichen Paramter? Das Problem lässt sich auch ohne diesen Paramter rekursiv lösen - ich sehe nicht einmal, warum dieser Parameter gut sein sollte!



  • Man muss ein Array nicht immer komplett weitergeben:

    #include <iostream>
    
    void print( int arr[], int len ) 
    {
            for( int i = 0; i < len; ++i ) {
                    std::cout << arr[i] << " ";
            }
    
            std::cout << "\n";
    }
    
    int main()
    {
            const int arr_len = 4;
            int arr[arr_len] = { 1, 2, 3, 4 };
    
            print( arr, arr_len);
            print( arr, arr_len - 1 );
            print( arr + 2, arr_len - 2 );
    }
    


  • Also das ist jetzt der gesamte Code:

    #include <iostream>
    using namespace std;
    
    //gibt den kleinsten Index zurück
    int min_index ( int a[], int i, int j )
    {
          if  (i == j)
              return i;
          //finde das kleinste der verbliebenden Elemente
          int k = min_index (a, i + 1, j);
          //gibt aus dem aktuellen und der verbliebenden Elemente das kleinste zurück
          return  ( a[i] < a[k] )? i : k;
    }
    
    void selectsort ( int a[], int size, int index = 0 )
    {
    
          // Ausgabe, wenn Anfang und size gleich sind
          if  ( index == size )
              return;
          // Aufruf der min_index Funktion, um den kleinsten Index zu erhalten
          int k = min_index ( a, index, size - 1 );
          // Tausche, wenn der kleinste Index ungleich dem Index ist
          if ( k != index )
              swap ( a[k], a[index] );
          // rekursiver Aufruf von selectsort
          selectsort ( a, size, index + 1 );
    }
    
    // Ausgabe des Arrays
    void ausgabe_a ( int a[], int size )
    {
          for ( int i = 0; i < size; ++i )
          {
            cout << a[i] << " ";
          }
        cout << endl;
    }
    
    int main ()
    {
          int a[] = { 4, 1, 5, 3, 2 };
          int size = sizeof ( a ) / sizeof ( a[0] );
    
          cout << "Array unsortiert: ";
          ausgabe_a(a, 5);
          cout << endl;
    
          selectsort (a, size);
    
          cout << "Array sortiert: ";
          ausgabe_a(a, 5);
          cout << endl;
    
    }
    

    wahrscheinlich bissel umständlich ^ ^



  • // rekursiver Aufruf von selectsort 
          selectsort ( a, size, index + 1 );
    

    manni66 schrieb:

    Man muss ein Array nicht immer komplett weitergeben

    welches zuerst das größte Element aus a findet

    Wie hängt das mit min_index zusammen?



  • In der Aufgabenstellung hieß es, dass das größte Element gefunden und nach hinten geschoben werden sollte. Du suchst das kleinste 🙂

    Daher:

    void selectsort(int a[], int size) {
        // Wir sind fertig, wenn das zu sortierende Array nur 1 Element lang ist
        if (size <= 1) return;
        // sonst: gröten Index finden
        int largestElementIdx = max_index(a, size);
        // ...und mit letztem Element tauschen
        if (largestElementIdx != size - 1) swap(a[largestElementIdx], a[size - 1]);
        // jetzt den Rest des Arrays sortieren
        selectsort(a, size - 1);
    }
    


  • manni66 schrieb:

    Man muss ein Array nicht immer komplett weitergeben

    Okay, ich habs jetzt noch mal anders geschrieben

    manni66 schrieb:

    welches zuerst das größte Element aus a findet

    manni66 schrieb:

    Wie hängt das mit min_index zusammen?

    Ja stimmt, es soll ja das größte genommen werden. Jetzt so:

    void selectsort ( int a[], int size )
    {
    
        int max_index = 0, temp = 0, index = 0;
        //finde das größte Element
        for ( index = max_index; index < size; ++index )
        {
            if ( a[index] > a[max_index] )
            {
                max_index = index;
            }
        }
        // hier wird getauscht
        temp = a[size-1];
        a[size-1] = a[max_index];
        a[max_index] = temp;
    
        if ( size > 1 )
        {
            // rekursiver Aufruf
            selectsort ( a, --size ) ;
        }
    }
    

    jetzt funktioniert's auch ohne den Zusatz von davor in der Signatur