[Pascal] bubblesort sortiert erst nach einigen durchläufen korrekt

[DX-Rated]

Hallo,

folgendes: Im Rahmen eines Programms zur Telefonnummernverwaltung habe ich ein bubblesort geschrieben, um die Datensätze sortiert ausgeben zu können. So weit, so gut. Wenn ich den (die? das?) bubblesort aufrufe, sortiert er aber noch nicht korrekt. Erst nach ein paar mal erhalte ich eine korrekt sortierte Liste.

weiter := true;


WHILE weiter = true DO

begin


      FOR i := 1 TO anz_eintr - 1 DO

          begin


            getauscht := false;

            if (datensatz[i].name > datensatz[i+1].name) then

               begin

                    datensatz[51]  := datensatz[i];

                    datensatz[i]   := datensatz[i+1];

                    datensatz[i+1] := datensatz[51];

                    getauscht      := true;

               end;


          end;


      if (getauscht = false) then

         begin

              weiter := false;

         end;

end;


(* Ausgabe von 8 Nachnamen zur Kontrolle *)

FOR i := 1 TO 8 DO

    begin

         gotoxy (11,9+i);

         writeln (datensatz[i].name);

    end;


repeat until keypressed;

anz_eintr enthält die Anzahl der in der Datenbank (bzw. dem Array) enthaltenen Datensätze. Das Programm soll 50 Datensätze speichern können. Datensatz 51 ist ein Hilfssatz zum Tauschen.

Die Ausgabe sieht nach den Aufrufen dieser Prozedur so aus:

1. mal: Chamnitz, Fiedler, Boller, Boese, Kempinski, Koen, Koslofski, Wernersen

2. mal: Chamnitz, Boller, Boese, Fiedler, Kempinski, Koen, Koslofski, Wernersen

3. mal: Boller, Boese, Chamnitz, Fiedler, Kempinski, Koen, Koslofski, Wernersen

4. mal: Boese, Boller, Chamnitz, Fiedler, Kempinski, Koen, Koslofski, Wernersen

Das ganze muss also 4 mal ablaufen, damit die Namen korrekt sortiert sind. Warum ist das so? Normalerweise sollte er doch alles in einem Rutsch sortieren? Was stimmt am Algorithmus nicht?

Natürlich könnte ich jetzt einfach 'ne Schleife drum packen, die das Ganze einige male hintereinander ausführt, aber das kann ja auch nicht Sinn der Sache sein.

[Klotzkopp]

Du darfst getauscht nicht bei jedem Schleifendurchlauf auf false setzen, sondern nur einmal, vor der Schleife. Sonst überschreibst du den true-Wert von einem vorausgegangenen Durchlauf ja wieder. Dadurch wird der Vorgang nur wiederholt, wenn das letzte und vorletzte Element vertauscht werden mussten.

[Pointerman]

Moin!

Auf diese Art und Weise kannte ich den Bubblesort noch gar nicht, ich habe das bis jetzt immer mit 2 Schleifen gemacht:

FOR iOberGrenze := anz_eintr-1 DOWNTO 1 DO

  FOR i := 1 to iObergrenze DO

    IF (datensatz[i].name > datensatz[i+1].name) then

    BEGIN

      iDummy  := datensatz[i];

      datensatz[i]   := datensatz[i+1];

      datensatz[i+1] := iDummy;

    END;

Da könnte man natürlich immernoch ein Abbruchkriterium rein bringen um es noch etwas zu beschleunigen.

@DX-Rated

Hast Du Dich eigentlich auf eine Array größe von 50 festgelegt? Ansonsten solltest Du vielleicht beim Tauschen datensatz[51] durch eine Puffervariable ersetzen.

[DX-Rated]

Du darfst getauscht nicht bei jedem Schleifendurchlauf auf false setzen, sondern nur einmal, vor der Schleife. Sonst überschreibst du den true-Wert von einem vorausgegangenen Durchlauf ja wieder. Dadurch wird der Vorgang nur wiederholt, wenn das letzte und vorletzte Element vertauscht werden mussten.

Jau, funktioniert jetzt! Dankeschön!

@Pointerman: Das Array habe ich auf eine Größe von 51 festgelegt. Ich lasse im Programm dann allerdings nur 50 Einträge zu. 51 ist ja nur zum tauschen da. Spielt es denn eine Rolle, ob ich zum Tauschen nur einen zusätzlichen Datensatz im Array oder eine eigenständige Variable (bzw. hier einen Record) nutze?

[Sill-el-Mot]

Auf diese Art und Weise kannte ich den Bubblesort noch gar nicht, ich habe das bis jetzt immer mit 2 Schleifen gemacht

Moin,

nur mal ne kleine Anmerkung: DX-Rated macht das ganze auch mit zwei schleifen. eine 'while'- und eine 'for'-Schleife. hab auch erst mal gesucht bis ich die erst schleife gesehen habe, aber mit nur einer schleife geht das imho nicht.

Gruß sillie

[tuxfriend]

Kleine Ergänzung:

Warum arbeitest du mit zwei Flags (getauscht und weiter)? Ein

getauscht:=true;

while getauscht do

begin

...

end;

würde reichen oder nicht?

[DX-Rated]

@tuxfriend: Wenn ich so drüber nachdenke hast Du eigentlich recht. Hab's aber noch nicht ausprobiert.

Ich bin aber im Rahmen des Debugging des Programms jetzt auf etwas anderes gestossen, was ich mir nicht wirklich erklären kann. Ich durchsuche die Datenbank nach dem ersten leeren Eintrag, damit ein neuer Datensatz hinzugefügt werden kann. Das mache ich über die vordefinierte Funktion length.

WHILE gefunden <> true DO

     begin

           i := i + 1;

           if (length(datensatz[i].name) = 0) then

                 gefunden := true;

     end;

Soweit, so gut. Beim ersten Datensatz zeigt er mir bei length auch korrekterweise die 7. Bei den folgenden Datensätzen kommen Nonsenszahlen raus (105, 112, etc. obwohl die Datensätze normal gefüllt sind). Der Wert für length(datensatz[5].name) ist dann schon 0, obwohl der Datensatz gefüllt ist und sich 12 Datensätze in der Datenbank befinden. :confused: