Zahlen sortieren, rekursive Funktion



  • 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.


Anmelden zum Antworten