Zahlen sortieren, rekursive Funktion



  • Hallo,

    meine Aufgabe ist es Zahlen, die eingelesen werden in einer rekursiven Funktion zu sortieren, leider habe ich nie zuvor Rekursionen verwendet und stehe etwas auf der Leitung.

    Die rekursive Funktion lässt sich am besten mit Zeigern lösen, der Zeiger muss dann das erste Feld nicht mehr mitberechnen. (siehe Text, bzw. Angabe)

    Angabe:

    Schreiben Sie ein Programm, das beliebig viele Zahlen (maximal 50) einliest und fallend sortiert wieder ausgibt. Verwenden Sie zum Sortieren folgenden rekursiven Algorithmus: Zunächst wird das Maximum gesucht und an die erste Stelle der Liste gesetzt. Dann wird dieser Vorgang mit der restlichen (um ein Element kürzeren) Liste wiederholt, so lange bis die Länge der Liste 1 ist.
    Bemerkung: Die Programmierung kann recht einfach erfolgen, wenn für die Liste ein globales Feld verwendet wird.

    #include <iostream>
    
    using namespace std;
    
    int feld[50]; 
    
    int maximum(int *n=feld) 
    { 
    	if (!n) // Welchen Ansatz brauche ich um die rekursive Funktion zu beenden?
    	return 0;
    
        int i=0, x[1], y, max=0;
    
        for(;feld[i]; i++) { 
    		if (feld[i] > max){ max = feld[i]; y = i;}; //das Maximum der Zahlen wird bestimmt
        } 
    
    	x[0] = feld[0]; //der größte Wert wird an den Anfang gesetzt
    	feld[0] = feld[y];
    	feld[y] = x[0];
    
    	for(int q = 0; feld[q];q++)
    	cout << feld[q] << endl;
    
    	return maximum(n++); // Wie verkürze ich den Zeiger auf das Feld richtig?
    }
    int main () {
    
    	cout << "Wieviele Zahlen möchten Sie eingeben?: " << endl;
    	int anzahl, i = 0;
    	cin >> anzahl;
    	cout << endl;
    
    	for(;i<anzahl;i++)
    		{
    		cin >> feld[i];	// Alle Werte werden eingelesen
    		}
    
    	cout << endl;
    	maximum();
    	cin >> i;
    
    return 0;
    }
    


  • Nimm so einen Funktionskopf:

    void maximum(int *n, int anzahl)
    {
      // Die for-Schleifen lauten jetzt:
      for (int i=0; i<anzahl; ++i) {
        ...
      }
    
      // Am Schluss:
      if (anzahl > 1)
        maximum(n+1, anzahl-1);
    }
    

    Das swappen kannst du übrigens auch noch einfacher implementieren.


  • Mod

    Ok, machen wir es mal mit Arrays. Ist in C++ zwar unnötig umständlich, aber wenn du auf Selbstquälerei stehst, ist das nicht mein Problem:

    int feld[50];
    

    Nicht nur, dass du Arrays benutzt, jetzt sind sie auch noch global. Extrem schlechter Stil und ganz ohne Not, dass du dies tust.

    int maximum(int *n=feld)
    
    • Ich dachte, die Funktion soll sortieren, warum heißt sie maximum?
    • Was soll der Returnwert? Vom Namen her würde man ja erwarten, dass ein Maximum zurückgegeben wird, aber das passt überhaupt nicht zu deinem Code. Und falls es eine Sortierfunktion auf einem Feld sein soll, dann ist der Rückgabewert doch wohl eher void.
    • int *n=feld Weißt du überhaupt, was das macht?
    • Wenn du schon Arrays benutzt, dann solltest du auch wissen, dass man die Größe mit übergeben muss.
    • Insgesamt: void sortieren(int *n, int size) wäre eine wesentlich geeignetere Funktionssignatur
    if (!n) // Welchen Ansatz brauche ich um die rekursive Funktion zu beenden?
    

    Jetzt wo du die Größe hast, wäre size==1 eine geeignete Abbruchbedingung

    return 0;
    

    Mir ist immer noch nicht klar, was der Returnwert überhaupt bedeuten soll. Falsl du meinen Vorschlag von oben übernimmst, gehört hier ein einfaches return hin.

    int i=0, x[1], y, max=0;
    
        for(;feld[i]; i++) {
            if (feld[i] > max){ max = feld[i]; y = i;}; //das Maximum der Zahlen wird bestimmt
        }
    
    • Was sind das für blöde Variablennamen? i geht ja noch als traditioneller Name für Zahlvariablen, aber x und y sagen überhaupt nichts aus.
    • Was soll die Abbruchbedingung?
    • Inwiefern ist 0 ein guter Startwert für max?
    • Hat es einen tieferen Sinn, i nicht innerhalb des Schleifenkopfes zu deklarieren?
    x[0] = feld[0]; //der größte Wert wird an den Anfang gesetzt
        feld[0] = feld[y];
        feld[y] = x[0];
    
    • Wozu muss dafür x vom Typ int[1] sein?
    • Wieso so umständlich? Wozu hast du dir denn sonst vorher das max gemerkt?
    for(int q = 0; feld[q];q++)
        cout << feld[q] << endl;
    

    Schon wieder eine völlig sinnlose Abbruchbedingung

    return maximum(n++); // Wie verkürze ich den Zeiger auf das Feld richtig?
    

    Warum willst du n um 1 erhöhen? Du willst doch bloß einen um eins größeren Wert an die Funktion übergeben, also n+1.



  • Danke, für die Kritik hatte sie dringend nötig!
    Echt vielen Dank, hat mir sehr weitergeholfen!

    Programm funktioniert jetzt.

    Habe, aber noch ein paar Fragen, um meine Programmierung für später zu verbessern!

    Warum ist das Anlegen eines Feldes umständlich? Alternativen?

    Wie vermeide ich in diesem Fall das globale Feld?

    Ich habe den kleinsten Integer Wert eingegeben, aber soviel ich weiß ist dieser ja in C++ nicht definiert, wie kann ich den kleinsten möglichen Integer Wert für jedes beliebe System, andem ich mein Programm ausführe ermitteln?

    Wie vermeide ich, das mehr als 50 Werte eingegeben werden, wenn die Anzahl der einzugebenden Werte nicht vorher definiert wurde?

    Kann ich mein Programm noch verbessern?

    #include <iostream>
    
    using namespace std;
    
    int feld[50]; 
    
    void sortieren (int *n, int size) 
    { 
    
        int positionmax, max=-2147483648;
    
        for(int i=0;n[i]; i++) { 
    		if (n[i] > max){ max = n[i]; positionmax = i;}; 
        } 
    
    	n[positionmax] = n[0];
    	n[0] = max;
    
    	  if (size > 1) 
        sortieren(n+1, size-1);
    
    	return;
    }
    int main () {
    
    	cout << "Wieviele Zahlen moechten Sie eingeben?: " << endl;
    	int anzahl;
    	cin >> anzahl;
    	cout << endl;
    
    	int size = 0;
    	for(;size<anzahl;size++)
    		{
    		cin >> feld[size];
    		}
    
    	cout << endl;
    
    	int *n=feld;
    	sortieren(n,size);
    
    		for(int q = 0; feld[q];q++)
    	cout << feld[q] << endl;
    
    	int i;
    	cin >> i;
    
    return 0;
    }
    


  • downandout schrieb:

    cout << "Wieviele Zahlen moechten Sie eingeben?: " << endl;
    int anzahl;
    cin >> anzahl;
    cout << endl;
    	
    int size = 0;
    for(;size<anzahl;size++) {
      cin >> feld[size];
    }
    
    cout << endl;
    
    int *n=feld;
    sortieren(n,size);
    

    Das hätte ich so umgeschrieben:

    cout << "Wieviele Zahlen moechten Sie eingeben?: " << endl;
    int anzahl;
    cin >> anzahl;
    int *feld = new int[anzahl]; // damit ersparst du dir das globale Array
    for (int i=0; i<anzahl; i++) {
      cin >> anzahl[size];
    }
    sortieren(feld, size);
    

    Das return auf Zeile 25 kannst du dir sparen und max (Z. 11) hätte ich mit n[0] initialisiert ;).


  • Mod

    downandout schrieb:

    Warum ist das Anlegen eines Feldes umständlich? Alternativen?

    Du könntest auch einen std::vector nehmen. Den kann man beliebig vergrößern und verkleinern, er hat eine Kopiersemantik und er kennt seine eigene Größe.

    Wie vermeide ich in diesem Fall das globale Feld?

    Indem du es nicht global machst? Warum ist es das im Moment überhaupt? Ich sehe nirgendwo, dass du diese Eigenschaft benutzt (und das ist auch gut so).

    Ich habe den kleinsten Integer Wert eingegeben, aber soviel ich weiß ist dieser ja in C++ nicht definiert, wie kann ich den kleinsten möglichen Integer Wert für jedes beliebe System, andem ich mein Programm ausführe ermitteln?

    1. Der kleinste Wert ist definiert. Iim climits-Header. Sowohl als Makro als auch in der Klasse numric_limits<int>.
    2. Aber besser: Setz es doch einfach auf den ersten Wert.

    Wie vermeide ich, das mehr als 50 Werte eingegeben werden, wenn die Anzahl der einzugebenden Werte nicht vorher definiert wurde?

    Das ist schon ok. Alternativ könntest du bei den Eingaben mitzählen. Die willkürliche Grenze 50 macht in der Aufgabenstellung aber an sich keinen Sinn. Würdest du std::vector benutzen, gäbe es gar keinen Grund sich einzuschränken.

    Kann ich mein Programm noch verbessern?

    Sieht recht gut aus. Frag aber auf jeden Fall noch ab, ob die eingegebene Anzahl auch kleiner als 50 ist. Ansonsten siehe oben. Dein Einrückungsstil ist noch ein wenig ungewöhnlich.

    edit: ⚠ Ganz wichtig! ⚠ Du hast keine Abbruchbedingung für die Rekursion!



  • @ Rekurs:

    Deine Schleifen-Abbruchbedingungen funktionieren so nicht - bzw. nur zufällig. Gib mal 5 Werte ein und eine 0 darin... Öha!

    Frage: was macht das n[i] (bzw. das feld[q]) in der for-Schleife?



  • oh, ich meinte @downandout...



  • SeppJ schrieb:

    Du hast keine Abbruchbedingung für die Rekursion!

    Die hat er doch?

    downandout schrieb:

    if (size > 1)
        sortieren(n+1, size-1);
    return;
    

  • Mod

    Rekurs schrieb:

    SeppJ schrieb:

    Du hast keine Abbruchbedingung für die Rekursion!

    Die hat er doch?

    downandout schrieb:

    if (size > 1)
        sortieren(n+1, size-1);
    return;
    

    Oh stimmt. Hatte zuerst gedacht, dass sie fehlt, weil ich nur am Anfang der Funktion geguckt habe, wo sie vorher stand.



  • Sepp3 hat in sofern recht: Die Abbruchbedingung der Rekursion ist am Beginn der Funktion oft geschickter. Warum:
    Was passiert, wenn das Feld nur 1 Element oder gar 0 hat?
    Die Eleganz der Rekursion kommt eigentlich in dem Moment, wo man zu Beginn

    if( size <= 1 ) return;
    

    sagen kann.



  • minstaros schrieb:

    @ Rekurs:

    Deine Schleifen-Abbruchbedingungen funktionieren so nicht - bzw. nur zufällig. Gib mal 5 Werte ein und eine 0 darin... Öha!

    Frage: was macht das n[i] (bzw. das feld[q]) in der for-Schleife?

    Wie meinst du das mit den Schleifen-Abbruchbedingungen, bzw. wie würdest das lösen?

    Schleife wird beendet sobald n[i] negativ wird also "False".



  • Rekurs schrieb:

    downandout schrieb:

    cout << "Wieviele Zahlen moechten Sie eingeben?: " << endl;
    int anzahl;
    cin >> anzahl;
    cout << endl;
    	
    int size = 0;
    for(;size<anzahl;size++) {
      cin >> feld[size];
    }
    
    cout << endl;
    
    int *n=feld;
    sortieren(n,size);
    

    Das hätte ich so umgeschrieben:

    cout << "Wieviele Zahlen moechten Sie eingeben?: " << endl;
    int anzahl;
    cin >> anzahl;
    int *feld = new int[anzahl]; // damit ersparst du dir das globale Array
    for (int i=0; i<anzahl; i++) {
      cin >> anzahl[size];
    }
    sortieren(feld, size);
    

    Das return auf Zeile 25 kannst du dir sparen und max (Z. 11) hätte ich mit n[0] initialisiert ;).

    Wie funktioniert dieser Zeiger auf ein new int Feld, welchen Geltungsbereich hat der Zeiger, das ganze Programm über auch in den Funktionen sobald dieser Befehl aufgerufen wurde? --> gibts da nicht einen delete() befehl dazu?!

    Warum sind globale Variablen überhaupt so eine schlimme Sünde? Ich arbeite bis jetzt gerne mit denen 😉


  • Mod

    downandout schrieb:

    Wie funktioniert dieser Zeiger auf ein new int Feld, welchen Geltungsbereich hat der Zeiger, das ganze Programm über auch in den Funktionen sobald dieser Befehl aufgerufen wurde? --> gibts da nicht einen delete() befehl dazu?!

    Vergiss das lieber mit dem new und delete. Das ist absolut kein Anfängerthema und hier absolut nicht angemessen. Das globale Array kannst du dir auch sparen, indem du die Definition einfach in die main schreibst, wo du das Array benutzt.

    Warum sind globale Variablen überhaupt so eine schlimme Sünde? Ich arbeite bis jetzt gerne mit denen 😉

    Sie machen dir bei komplexen Programmen das Leben zur Hölle.



  • downandout schrieb:

    minstaros schrieb:

    @ Rekurs:

    Deine Schleifen-Abbruchbedingungen funktionieren so nicht - bzw. nur zufällig. Gib mal 5 Werte ein und eine 0 darin... Öha!

    Frage: was macht das n[i] (bzw. das feld[q]) in der for-Schleife?

    Wie meinst du das mit den Schleifen-Abbruchbedingungen, bzw. wie würdest das lösen?

    Schleife wird beendet sobald n[i] negativ wird also "False".

    Nö - n[i] kann ruhig negativ sein - das führt zu keinem Abbruch (und soll es ja auch nicht). Wenn n[i] allerdings 0 ist wird abgebrochen.
    Will man das? Nein. Es könnte doch durchaus sein, dass man die Zahl 0 eingegeben hat. Das soll natürlich nicht zu einem Abbruch führen.



  • downandout schrieb:

    Wie meinst du das mit den Schleifen-Abbruchbedingungen, bzw. wie würdest das lösen?

    Schleife wird beendet sobald n negativ wird also "False".

    *Vorsicht, Du verwechselst ein paar Dinge.

    • For-Schleifen laufen so lange, so lange die Bedingung im mittleren Argument "wahr" ist. Das ist in den meisten Fällen ein Vergleich (z.B. i < 5 ), kann aber auch eine Variable/Pointer oder ein Funktionsaufruf sein.
    • "wahr" (besser: true) ist alles, was nicht gleich 0 ist, d.h. umgekehrt 0 --> false. Hat also mit negativem oder positivem Wertebereich nichts zu tun. Zudem: Wie sollte ein n[ i ] in Deinem Sortierarray auf einmal negativ werden?
    • n[ i ] entspricht dem Inhalt des Elements i Deines Arrays. Wenn Du also z.B. 5 Elemente hast, wird beim Durchlauf mit i==5 bereits der Inhalt des 6. Elements angesprochen. Dieses liegt bereits hinter dem erlaubten Bereich: Du darfst aber nur die Elemente n[0] bis n[4] verwenden!
      Nur durch Zufall waren bei Deinen Probeläufen die anderen Elemente auch 0, daher hat die Schleife scheinbar korrekt abgebrochen, aber da das Array nicht initialisiert ist, kannst Du Dich nicht darauf verlassen. Wenn nämlich alle Elemente des Array-Speichers zufällig != 0 sind (und ggf. auch die 10000 Bytes danach), wird Deine Schleife "etwas" mehr zu tun bekommen. Und da im Anschluß noch Elemente in diesem Speicher kopiert werden, knallt es. Eine Art Buffer overflow.

    Ein weiterer Punkt ist die Variable positionmax. Da diese nicht initialisiert wird, kann jeder beliebige Wert drin stehen! Was passiert nun mit positionmax, wenn Du sortieren( ) mit size = 0 aufrufst? (Unabhängig der Diskussion, ob das [i]sinnvoll* ist: Es ist möglich, und ein size vom Typ int erlaubt auch eine 0, daher muss man das berücksichtigen. Korrekter wäre übrigens ein unsigned int.)



  • PS: Das Problem mit positionmax besteht auch bei beliebigem size, wenn die Liste vorher bereits korrekt sortiert ist (beobachte positionmax im Zusammenhang mit der if-Abfrage in der For-Schleife).



  • minstaros schrieb:

    downandout schrieb:

    Wie meinst du das mit den Schleifen-Abbruchbedingungen, bzw. wie würdest das lösen?

    Schleife wird beendet sobald n negativ wird also "False".

    *Vorsicht, Du verwechselst ein paar Dinge.

    • For-Schleifen laufen so lange, so lange die Bedingung im mittleren Argument "wahr" ist. Das ist in den meisten Fällen ein Vergleich (z.B. i < 5 ), kann aber auch eine Variable/Pointer oder ein Funktionsaufruf sein.
    • "wahr" (besser: true) ist alles, was nicht gleich 0 ist, d.h. umgekehrt 0 --> false. Hat also mit negativem oder positivem Wertebereich nichts zu tun. Zudem: Wie sollte ein n[ i ] in Deinem Sortierarray auf einmal negativ werden?
    • n[ i ] entspricht dem Inhalt des Elements i Deines Arrays. Wenn Du also z.B. 5 Elemente hast, wird beim Durchlauf mit i==5 bereits der Inhalt des 6. Elements angesprochen. Dieses liegt bereits hinter dem erlaubten Bereich: Du darfst aber nur die Elemente n[0] bis n[4] verwenden!
      Nur durch Zufall waren bei Deinen Probeläufen die anderen Elemente auch 0, daher hat die Schleife scheinbar korrekt abgebrochen, aber da das Array nicht initialisiert ist, kannst Du Dich nicht darauf verlassen. Wenn nämlich alle Elemente des Array-Speichers zufällig != 0 sind (und ggf. auch die 10000 Bytes danach), wird Deine Schleife "etwas" mehr zu tun bekommen. Und da im Anschluß noch Elemente in diesem Speicher kopiert werden, knallt es. Eine Art Buffer overflow.

    Ein weiterer Punkt ist die Variable positionmax. Da diese nicht initialisiert wird, kann jeder beliebige Wert drin stehen! Was passiert nun mit positionmax, wenn Du sortieren( ) mit size = 0 aufrufst? (Unabhängig der Diskussion, ob das [i]sinnvoll* ist: Es ist möglich, und ein size vom Typ int erlaubt auch eine 0, daher muss man das berücksichtigen. Korrekter wäre übrigens ein unsigned int.)

    Hat n[ i ] kein /0 Array? n[] muss ja irgendwann auf dieses /0 treffen und dann brichts ja automatisch ab wegen false oder? Oder versteh ich da jetzt was falsch?!

    positionmax wird ja eh nicht verwendet oder? und erst nachher zugewiesen.. So schlimm? Oder meint ihr das das Spielraum für Fehler lässt?



  • downandout schrieb:

    Hat n[ i ] kein /0 Array? n[] muss ja irgendwann auf dieses /0 treffen und dann brichts ja automatisch ab wegen false oder? Oder versteh ich da jetzt was falsch?!

    positionmax wird ja eh nicht verwendet oder? und erst nachher zugewiesen.. So schlimm? Oder meint ihr das das Spielraum für Fehler lässt?

    Nein, Arrays sind keine Strings. Wenn Du ein Array machst mit 5 Elementen, dann hast Du genau diese 5 Element, und jedes davon kann dann alle int-Werte enthalten (von -xxx bis +xxx einschließlich 0). Ein Array weiß die Anzahl seiner Elemente nicht, es ist nur der dafür benötigte Speicherbereich. Daher musst Du Dir die Anzahl getrennt davon merken, daher die Variable size.

    Deswegen haben ja schon einige andere hier empfohlen, den in der C++ Stantardbibliothek angebotenen Container "vector" zu verwenden, denn ein Vector kennt seine Größe. Aber bleib erstmal beim Array, da lernst Du mehr.

    Nochmal zurück zu Deiner ersten Frage: Ja, die Schleife bricht ab, wenn ein Element 0 ist, aber das ist auch der Fall, wenn Du eine 0 zwischen all den zu sortierenden Zahlen hast. Folge: Du kannst n[ i ] nicht als Abbruchbedingung nehmen.

    Bis wann willst Du die Schleife laufen lassen? Antwort: bis der Zähler i das letzte Element erreicht hat (einschließlich). Und das ist (beim Beispiel mit 5 Elementen) der Fall bei i == 4. So, zudem hast Du die Variable "size" mit Inhalt 5. Nun, was setzt Du also als Abbruchbedingung ein?

    Zur zweiten Frage: Richtig, posistionmax wird unter Umständen gar nicht verwendet. Da die Variable aber nicht initialisiert wird, kann jeder beliebige Wert darin stehen (es wird nicht automatisch 0 reingeschrieben, wie das noch bei BASIC war!).

    Nach der For-Schleife kommt dann das "n[ positionmax ] = n[ 0 ] ...", das heißt, Du schreibst an eine beliebige Speicherzelle! Könnte sein, dass Dein Betriebssystem das gar nicht mag und eine Speicherschuzverletzung ausgibt.


Log in to reply