Schleife falsch aufgebaut

[Enrico0304]

Hallo zusammen,

ich habe folgendes Problem: beim Aufrufen der Prozedur wird diese zwar ausgeführt, allerdings wird auch der Ausgabeteil am Ende genau so oft durchlaufen, wie ich Zufallszahlen im Array habe. Offensichtlich habe ich die Schleife falsch aufgebaut, kann aber beim besten Willen den Fehler nicht finden.

Kann mir bitte jemand einen Hinweis geben ?

Ich arbeite nur mit konsolenbasiertem Pascal (Vorgabe Schule) und mit CharmPascal 2.5 (meine Wahl).

Code: Alles auswählen

    procedure QuicksortMitStatistik(var Zufallszahlen: ZufallszahlenArray; Links, Rechts: Longint);
    var
    i, j, Pivot, Temp, Vergleiche: Longint;
    Startzeit, Endzeit: TDateTime;
    Zeitdauer: TTime;
    begin
        Vergleiche := 0;
        Startzeit  := Now; // Aufzeichnung der Startzeit
        if Links < Rechts then
        begin
            Pivot := Zufallszahlen[(Links + Rechts) div 2];
            i := Links;
            j := Rechts;
            while i <= j do
            begin
                while Zufallszahlen[i] < Pivot do
                    i := i + 1;
                while Zufallszahlen[j] > Pivot do
                    j := j - 1;
                if i <= j then
                begin
                    Temp := Zufallszahlen[i];
                    Zufallszahlen[i] := Zufallszahlen[j];
                    Zufallszahlen[j] := Temp;
                    i := i + 1;
                    j := j - 1;
                    Vergleiche := Vergleiche + 1;
                end;
            end;
            QuicksortMitStatistik(Zufallszahlen, Links, j);
            QuicksortMitStatistik(Zufallszahlen, i, Rechts);
        end;
        Endzeit   := Now; // Aufzeichnung der Endzeit
        writeln('Anzahl der Vergleiche: ', Vergleiche);
        writeln('Startzeit: ', FormatDateTime('hh:nn:ss:zzz', Startzeit));
        writeln('Endzeit: ', FormatDateTime('hh:nn:ss:zzz', Endzeit));
        Zeitdauer := Endzeit - Startzeit;
        writeln('Gemessene Zeitdauer: ', FormatDateTime('hh:nn:ss:zzz', Zeitdauer));
    end;

[ArchChem]

Hallo,

du rufst die Prozedur aus der Prozedur heraus auf (Rekursion), wodurch der Anfang (Beginn der Zeitrechnung) und das Ende (der Ausgabenteil) natürlich jedes Mal auch ausgeführt wird, da du keine vorherige Abzweigung aufgebaut hast. Dadurch, dass deine Zeitvariablen lokal sind (also immer nur für die jeweilige Prozedur gelten), erhältst du auch keine Gesamtzeit. Du hast zwei Möglichkeiten, das zu ändern:

1. Nutze eine Rahmenprozedur, welche die Zeitmessung startet, deine Quicksort-Prozedur aufruft (welche dann nur noch das Sortieren und nicht die Zeitmessung übernimmt), und am Ende die Zeit ausgibt. Das würde ich empfehlen, da du diese Rahmenprozedur dann ggf. auch für andere Prozeduren verwenden kannst.

2. Baue deine jetzige Prozedur so um, dass nur am Ende die Gesamtzeit ausgegeben wird und bis dahin die jeweiligen Teilzeiten aufaddiert werden. Das ist möglich, aber ein bisschen komplizierter.

[Enrico0304]

Hallo ArchChem,

Danke für die Hinweise !

Ich glaube, verstanden zu haben, wo ich den Fehler machte. Werde nun versuchen Lösungsansatz 1 umzusetzen.

Danke & Gruß
Enrico

[ArchChem]

Hallo Enrico,

gerne und viel Freude bei der Umsetzung!

Viele Grüße
ArchChem

[Enrico0304]

Guten Abend,
ich mache Fortschritte, aber wohl noch nicht in die richtige Richtung.
Meine kleine, schlanke Prozedur für die Statistik, aus der ich die (angepasste) Quicksort-Prozedur aufrufe, führt zu folgendem Ergebnis: Sortierung i.O., Zähler der Vergleiche zählt von 1 hoch, fällt aber während der Prozedur manchmal wieder 1 oder mehr Zähler zurück (?!?!!?) und wird am Ende ohnehin wieder auf „null“ gesetzt.
Die Zeiten sind plausibel.
Irgendwie habe ich den Zähler falsch positioniert. Mein Versuch ebendiesen in eine weitere Prozedur auszulagern scheiterte ebenfalls.

Googlen nach „Zähler in rekursiver Schleife“ liefert keine Ergebnisse die mich weiterbringen.
Für Hinweise oder Tipps bin ich echt dankbar !

Code: Alles auswählen

procedure StatistikFuerQuicksort(var Zufallszahlen: ZufallszahlenArray; AnzahlZufallszahlen: longint);
var
Vergleiche, Zaehler: longint;
Startzeit, Endzeit, Zeitdauer: TDateTime;

begin
    Vergleiche := 0;
    Zaehler    := 0;
    Startzeit  := Now; // Aufzeichnung der Startzeit
    
    Quicksort(Zufallszahlen, 0, AnzahlZufallszahlen - 1,Vergleiche);
    
    Endzeit   := Now; // Aufzeichnung der Endzeit
    //Ausgabe Statistik
    writeln('Anzahl der Vergleiche: ', Vergleiche);
    writeln('Anzahl der Vergleiche 2: ', Zaehler);
    writeln('Startzeit: ', FormatDateTime('hh:nn:ss:zzz', Startzeit));
    writeln('Endzeit: ', FormatDateTime('hh:nn:ss:zzz', Endzeit));
    Zeitdauer := Endzeit - Startzeit;
    writeln('Gemessene Zeitdauer: ', FormatDateTime('hh:nn:ss:zzz', Zeitdauer));
   end;

Code: Alles auswählen

procedure Quicksort(var Zufallszahlen: ZufallszahlenArray; Links, Rechts, Vergleiche: Longint);
var
  i, j, Pivot, Temp {,Vergleiche}: Longint;
begin
  if Links < Rechts then
  begin
    Pivot := Zufallszahlen[(Links + Rechts) div 2];
    i := Links;
    j := Rechts;
    while i <= j do
    begin
      while Zufallszahlen[i] < Pivot do
        i := i + 1;
      while Zufallszahlen[j] > Pivot do
        j := j - 1;
      if i <= j then
      begin
        Temp := Zufallszahlen[i];
        Zufallszahlen[i] := Zufallszahlen[j];
        Zufallszahlen[j] := Temp;
        i          := i + 1;
        j          := j - 1;
        Vergleiche := Vergleiche + 1;
        writeln('Anzahl der Vergleiche: ', Vergleiche); // Testausgabe => zeigt ob Zähler angesprochen wird
        counter();
      end;
    end;
    Quicksort(Zufallszahlen, Links, j,Vergleiche);
    Quicksort(Zufallszahlen, i, Rechts,Vergleiche);
  end;
end;

Code: Alles auswählen

procedure counter();
  var 
  Zaehler: longint;
  begin
      Zaehler := Zaehler + 1;
  end;

Ergebnis:

Code: Alles auswählen

Anzahl der Vergleiche: 1
Anzahl der Vergleiche: 2
Anzahl der Vergleiche: 3
Anzahl der Vergleiche: 4
Anzahl der Vergleiche: 5
Anzahl der Vergleiche: 6
Anzahl der Vergleiche: 7
Anzahl der Vergleiche: 7
Anzahl der Vergleiche: 8
Anzahl der Vergleiche: 9
Anzahl der Vergleiche: 10
Anzahl der Vergleiche: 10
Anzahl der Vergleiche: 8
Anzahl der Vergleiche: 6
Anzahl der Vergleiche: 7
Anzahl der Vergleiche: 8
Anzahl der Vergleiche: 9
Anzahl der Vergleiche: 10
Anzahl der Vergleiche: 11
Anzahl der Vergleiche: 12
Anzahl der Vergleiche: 13
Anzahl der Vergleiche: 14
Anzahl der Vergleiche: 15
Anzahl der Vergleiche: 15
Anzahl der Vergleiche: 13
Anzahl der Vergleiche: 9
Anzahl der Vergleiche: 10
Anzahl der Vergleiche: 10
Anzahl der Vergleiche: 0
Anzahl der Vergleiche 2: 0
Startzeit: 20:09:21:164
Endzeit: 20:09:21:180
Gemessene Zeitdauer: 00:00:00:016

Gruß Enrico

[charlytango]

Aus meiner Sicht ist nicht die Schleife falsch.
Du hast ein Problem mit dem Gültigkeitsbereich von Variablen.

Die Prozedur counter() zählt eine lokale variable zaehler hoch, die zudem noch keinen Basiswert hat und auch nichts zurückgibt.

Dein Problem kann auf zwei Arten gelöst werden:
Unschön: Mit einer globalen Variablen (einer die im ganzen Programm sichtbar ist) die vor dem Sort resettet und in der rekursiven Funktion erhoht wird.

Eleganter: Du reichst eine Zählervariable in die rekursive Funktion durch und erhöhst sie dort.

[Enrico0304]

Hallo charlytango,

danke für die Hinweise !
Ich habe es mit der "rustikalen" Variante zum fliegen bekommen !

Die andere Variante probiere ich auch, wird allerdings erst nöchste Woche.
Ich werde berichten !

Trotzdem Danke ans Forum ! Mission accomplished !!!

Gruß Enrico