Zahlen sortieren - Problem mit Bubblesort

johann2193 · Hält's aus hier Beiträge: 2

Hallo,

wir sollen mit Hilfe von Bubblesort ein Programm erstellen, das zwei Memos enthält. In das linke soll man Zahlen reinschreiben können, wenn man auf den Button "sortieren" klickt, sollen die Zahlen im rechten Memo der Größe nach sortiert werden.

Leider funktioniert mein Quelltext nicht, biiiiiiiiiiiiiiiiiiiiiitte helft mir. Es wird benotet -,-

Hier der Quelltext:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

procedure TForm1.Button1Click(Sender: TObject);
var feld1, feld2: array of integer; 
    i,länge,speicher: integer;
    fertig: boolean;
begin
    länge:=memo1.Lines.Count;
    setlength(feld1,länge);
    fertig:=false;

    for I := 0 to length(feld1)-1 do
    feld[i]:=StrToInt(Memo1.Lines[i]);
    
while fertig=false do
begin
  fertig:=true;
   for I:= 0 to length(feld1)-2 do
    begin

      if feld[i]>feld[i+1] then
      begin
        speicher:=feld[i];
        feld1[i]:=feld1[i+1];
        feld1[i+1]:=Speicher;
        if feld[i]<feld1[i-1] then
        fertig:=false;
      end;
     
     end;
end;
     for I := 0 to length(feld1)-1 do

     memo2.Lines.Add(IntToStr(Feld1[i]));
end;

Moderiert von Gausi: Delphi-Tags hinzugefügt

Gausi · Verfasst: Do 01.12.11 22:52

Hallo und

in der Entwickler-Ecke,

das einzige, was mir da auffällt ist die zusätzliche Abfrage vor dem Setzen von Fertig - die gehört da nicht hin. Wenn einmal vertauscht wurde, ist man nicht fertig.

Also:

markieren

Delphi-Quelltext

1:
2:

//if feld[i]<feld1[i-1] then // Das einfach auskommentieren, fertig auf jeden Fall auf False setzen.
        fertig:=false;

Und: man sollte nicht auf False oder True testen, sondern besser so:

markieren

Delphi-Quelltext

1:	while not fertig do

_________________
We are, we were and will not be.

johann2193 · Hält's aus hier Beiträge: 2

Danke dir vielmals für die Antwort

Mal gucken, hoffentlich geht es dann morgen wenn ich das noch ändere

bummi · Verfasst: Do 01.12.11 23:42

da sind noch ein paar feld[i] drin wo eigentlich feld1[i] gemeint ist, oder Du benennst alles in Feld um und schmeißt Feld2 raus.

_________________
Das Problem liegt üblicherweise zwischen den Ohren H₂♂
DRY DRY KISS

Delphi-Laie · Verfasst: Fr 02.12.11 00:33

Und was mir auffällt: Bubblesort funktioniert mit zwei ineinander verschachtelten Schleifen. Mit nur einer Schleife kann es nicht sortieren.

Frisch aus meinem Sortierkino kopiert:

markieren

Delphi-Quelltext

1:
2:
3:

for x:=0 to Elementeanzahl-2 do 
  for y:=pred(Elementeanzahl) downto succ(x) do
    if Menge[pred(y)].schluessel>Menge[y].schluessel then tausche(pred(y),y)

Dabei kann man die innere und die äußere Schleife voneinander unabhängig jeweils beliebig von unten nach oben oben umgekehrt laufen lassen, aber das nur nebenbei. Eine funktionerende Lösung reicht ja erst einmal.

Der Vergleich auf false (=false) ist auch nicht gerade elegant. while not fertig ist es hingegen eher. Edit: Ich sehe gerade, daß letzteres Gausi schon richtigstellte.

Gausi · Verfasst: Fr 02.12.11 08:42

@Delphi-Laie: Die Variante mit der äußeren While-Schleife ist eine der gängigen "Optimierungen" beim Bubblesort. Dann hat man im Best-Case eine lineare Laufzeit, da bei einem sortierten Feld nach einem Durchlauf schon keine Vertauschung durchgeführt wurde, das Flag "fertig" dann wahr bleibt und das Verfahren abbricht.

_________________
We are, we were and will not be.

Dude566 · Verfasst: Fr 02.12.11 12:17

Die Variante von user profile icon

Delphi-Laie wird oft in Schulen gelehrt, ist meine Erfahrung.

Ich selbst finde die Variante die user profile icon

Gausi nannte aber auch besser:
www.delphi-treff.de/...ortieren/bubblesort/

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Delphi-Laie · Verfasst: Sa 03.12.11 19:11

Also, meine "Optimierung" des Bubblesorts bestand zunächst nur darin, statt der Vertauschungen zyklische Verschiebungen durchzuführen, das verringerst die Anzahl der Verschiebungen (jeder Tausch wird ja schließlich mit zyklischer (3er)Verschiebung realsisiert). Das ist natürlich nicht adaptiv gegenüber (vor-)sortierten Startmengen. Bubblesort ist dermaßen niedrig im algorithmischen Niveau, daß ich über weitere Verbesserungen nicht nachdachte. Grundsätzlich läßt sich ja in jeden (m.E. nicht nur vergleichsbasierten, sondern wirklich vor jeden) Sortieralgorithmus eine Anfangsprüfschleife, die die "Schon-Sortiertheit" überprüft, implementieren.

Eine runde Stunde (erstaunlich, wie das schnöde Bubblesort einen beschäftigen kann) benötigte ich, um die hier erwähnten Optimierungen einzubauen.

Mein - nunmehr adaptives, also i.S.v. (Vor-)Sortierungen "intelligentes" - Bubblesort fängt bei kompletter Sortiertheit zum Begin gar nicht erst richtig an (eben nur Prüfung und dann Ende) und ist bei Vorsortierungen schneller fertig, weil es die Sortiertheit erkennt und daraufhin abbricht; es sieht nun so aus:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

{z_sortierelement ist vom Typ "Sortierelement", welcher im Prinzip beliebig (komplex) aufgebaut sein kann,
aber auf jeden Falle ein sog. Schlüsselelement (Teilelement) für die Vergleiche enthalten muß; im einfachsten
Falle besteht die zu sortierende Menge aus simplen, größenvergleichbaren Elementen wie Zahlen (real oder integer)
oder Strings. Dann sind diese Elemente gleich dem Schlüssel(element), also sozusagen ihr eigener Schlüssel.}

for x:=0 to Elementeanzahl-2 do
  begin
  p:=true;

  z_sortierelement:=Menge[pred(Elementeanzahl)];
  for y:=pred(Spaltenanzahl) downto succ(x) do
    if Menge[pred(y)].schluessel>z_sortierelement.schluessel then
      begin
      Menge[y]:=Menge[pred(y)];
      p:=false
      end
    else
      begin
      if not p then Menge[y]:=z_sortierelement;
      z_sortierelement:=Menge[pred(y)]
      end;
  if p then break;
  Menge[x]:=z_sortierelement
  //Menge[y]:=z_sortierelement //identisch, da y=x
  end;

Edit: Wie der Algorithmus des Diskussionseröffners sortieren soll, ist mir nach wie vor schleierhaft. Natürlich kann man äußerlich eine while- oder repeat-Schleife implementieren, um den Abbruch zu erleichtern (ich benutzte break), dennoch benötigt man zwei ineinandergeschachtelte Zähl- oder wenigstens zählende Schleifen für Bubblesort. Das kann so nicht sortieren, meine ich also weiterhin.

Edit 2: Die innere Schleife kann/könnte im Verlaufe der Sortierung immer kürzere Bereiche der Sortiermenge durchlaufen, weil der sortierte Anteil der Menge im Verlaufe der Sortierung immer mehr zunimmt (es gibt auch Sortierungen, die umgekehrt arbeiten, indem diese die Sortiermenge insgesamt allmählich immer mehr sortieren). Deshalb wird die innere Zählschleife unnötig oft durchlaufen.

newi10 · Hält's aus hier Beiträge: 12 Erhaltene Danke: 1

Hallo hier meine Antwort

variablen-namen dürfen nie ä ö o. ü enthalten variable feld gibt es nicht sondern nur feld1
habe quelltext überarbeitet - bei mir gehts - hoffe - du bekommst gute note

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

procedure TForm1.Button1Click(Sender: TObject);
var feld1, feld2: array of integer; 
    i,laenge,speicher: integer;
    fertig: boolean;
begin
    laenge:=memo1.Lines.Count;
    setlength(feld1,laenge);
    fertig:=false;

    for I := 0 to length(feld1)-1 do
    feld1[i]:=StrToInt(Memo1.Lines[i]);

while fertig=false do
begin
  fertig:=true;
   for I:= 0 to length(feld1)-2 do
    begin

      if feld1[i]>feld1[i+1] then
      begin
        speicher:=feld1[i];
        feld1[i]:=feld1[i+1];
        feld1[i+1]:=Speicher;
        if feld1[i]<feld1[i-1] then
        fertig:=false;
      end;
     
     end;
end;
     for I := 0 to length(feld1)-1 do

     memo2.Lines.Add(IntToStr(Feld1[i]));
end;

Moderiert von Martok: Delphi-Tags hinzugefügt

Delphi-Laie · Verfasst: Sa 03.12.11 23:12

Und weil es so schön ist, hier noch gleich die etwas einfachere Variante, die zwar auch (vor-)sortierte Mengen "erkennt", also demgegenüber "intelligent" ist und mit Laufzeitverkürzungen darauf "reagiert" (Terminus: adaptiv), jedoch mit den klassischen Vertauschungen fungiert:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

for x:=0 to Elementeanzahl-2 do
  begin
  p:=true;
  for y:=pred(Elementeanzahl) downto succ(x) do
    if Menge[pred(y)].schluessel>Menge[y].schluessel then
    begin
    //Vertauschung über "Ringtausch" mit 3 Wertezuweisungen
    z_sortierelement:=Menge[y];
    Menge[y]:=Menge[pred(y)];
    Menge[pred(y)]:=z_sortierelement
    p:=false
    end;
  if p then break
  end;

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme