Entwickler-Ecke :: Thema anzeigen - Zahlen sortieren

johann2193 - Do 01.12.11 22:46
Titel: Zahlen sortieren - Problem mit Bubblesort

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:

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 - Do 01.12.11 22:52

Hallo und :welcome: 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:

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:

Delphi-Quelltext

1:	while not fertig do

Delphi-Laie - 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:

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.

Delphi-Laie - 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:

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 - Sa 03.12.11 21:12

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

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 - 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:

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;

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!