Bubble-Sort
Hallo,
ich habe grade ein bissell nach dem Sortier-Algo Bubble-Sort gesucht hab da auch was gefunden:
Delphi-Quellcode:
ist ja auch schön und gut...könnte mir jetzt nur mal bitte jemand die procedur vertauschen erklären...
procedure vertauschen(var a, b: Char);
var h: Char; begin h:= a; a:= b; b:= h; end; procedure TForm1.Button1Click(Sender: TObject); var word1, word2 : string; anzahl,j,k,w:integer; begin word1:=edit1.text; word2:=edit1.text; anzahl:=length(word1); for j:=anzahl downto 1 do begin for k:=1 to j do begin if (word2[k-1]>word2[k]) then vertauschen(word2[k-1], word2[k]); end; end; edit2.text:=word2; end; Außerdem kappier ich das ab der 1. for - Schleife nicht wirklích :( |
Re: Bubble-Sort
Zitat:
Delphi-Quellcode:
procedure vertauschen(var a, b: Char);
var h: Char; begin h := a; // Den Wert von a in h 'sichern' a := b; // Den Wert von b nach a schreiben b := h; // Den alten gesicherten Wert von a nach b schreiben end; |
Re: Bubble-Sort
Nachtrag: Wie der Bubblesort genau tut steht übrigens recht gut im Tutorial Sortieralgorithmen I + II von Cheffe^^
|
Re: Bubble-Sort
okey das ist klar aber wie arbeiten die verschiedenen for schleifen miteinander und dann die zeile
Delphi-Quellcode:
if (word2[k-1]>word2[k]) then vertauschen(word2[k-1], word2[k]);
|
Re: Bubble-Sort
Delphi-Quellcode:
Anzahl is die Länge des Strings.
for j:=anzahl downto 1 do
begin for k:=1 to j do begin if (word2[k-1]>word2[k]) then vertauschen(word2[k-1], word2[k]); end; end; Dann geht er rückwärts durch den string durch und vergleicht jede zahl mit den anderen im String. wo er dann aber das sortierte zurück gibt .... seh ich gerade nicht oO :gruebel: |
Re: Bubble-Sort
@netscanner
Zitat:
Position [k-1] mit [k] Grüße Klaus |
Re: Bubble-Sort
klaus... das hab ich ja nicht geschrieben ... *hust* ... :twisted:
|
Re: Bubble-Sort
@Schaedel:
Delphi-Quellcode:
dort gibt er den Wert zurück :)
edit2.text:=word2;
|
Re: Bubble-Sort
Hallo,
wenn die Prozedur vertauschen aufgerufen wird, werden ihr 2 Zeichen übergeben, die in a und b gespeichert werden. a wird dann in h zwischengespeichert. dann wird a zu b und b wird zu h, also dem alten a-Wert Zur Erklärung des Restlichen: Du hast 2 for-Schleifen. Angenommen du hast das Wort HILFE Jetzt durchläufst du das Wort HILFE mit EINER For-Schleife. Dann vergleichst du im 1. Schritt H und I, H ist kleiner als I also nicht vertauschen Dann vergleichst du im 2. Schritt I und L, I ist kleiner als L also nicht vertauschen Dann vergleichst du im 3. Schritt L und F, L ist größer als F also vertauschen Hier zeigt sich für mich ein Fehler in vertauschen: außer die Buchstaben in beliebigen Variablen zu tauschen, wird nichts gemacht. Das Wort HIFLE sollte irgendwo gespeichert werden um damit weiterarbeiten zu können. z.B. durch word2[k-1]:=a und word2[k]:=b In Folge dessen zeigen sich aber noch mehr Schwächen in dem Programm. Hast du die Schleife beendent, in diesem Fall die innere Schleife, erhälst du das Wort HIFEL Jetzt musst du die Sortierung aber nochmal drüberlaufen lassen, denn jeder Buchstabe wird ja nur um einen Platz verschoben, wenn es nötig ist. Im schlimmsten Fall steht ganz hinten ein A und muss nach ganz vorne gebracht werden. Daher brauchst du also eine zweite Schleife. Der Algorithmus den du vorgelegt hast, berücksichtigt die letzte Stelle des Wortes allerdings nur beim 1. Durchgang, was für mich nicht verständlich ist. Gruß Minz |
Re: Bubble-Sort
Zitat:
|
Re: Bubble-Sort
also nur als info an alle:
das programm läuft ohne probleme... @schaedel & minz: eure einwände erscheinen mir als logisch...aber warum läuft das programm dann ohne probleme...hilfe wird z.b. 100% richtig sortiert... außerdem gibt es ja 2 for schleifen also weiß ich jetzt nicht genau worauf ihr hinaus wollt,,, wie würdet ihr es denn schreiben? |
Re: Bubble-Sort
Delphi-Quellcode:
for j:=anzahl downto 1 do
begin for k:=1 to j do begin if (word2[k-1]>word2[k]) then vertauschen(word2[k-1], word2[k]); end; end; auch auf die Gefahr hin das ich mich unbeliebt mache, aber wenn k=1 ist wird word2[0] mit word2[1] verglichen -> da kann nicht gescheites bei herauskommen da in word[0] die Längeinformation des Strings steht.
Delphi-Quellcode:
Hoffe hab' mich nicht zu sehr verhauen.
for j:= 1 to anzahl -1 do
for k:=j+1 to anzahl do if word2[k] > word2[j] then vertausche(word2[k],word2[j]) Grüße Klaus |
Re: Bubble-Sort
okey klaus...aber dann füg doch mal den code bei dir in delphi ein und teste ihn...bei mir mach er bei der vertauschung keinen fehler...
|
Re: Bubble-Sort
Zitat:
|
Re: Bubble-Sort
Zitat:
Und eben diese Variable wird zum Schluss wieder dem Edit zugewiesen. Ist meines Erachtens absolut korrekt. |
Re: Bubble-Sort
gut funktioniert!
.. aber auch wenn Du k von 2 starten läßt und funktioniert nicht korrekt wenn Du auf word2[k-1] < word2[k] vergleichst. Das Problem tritt auch nur dann auf wenn Du mit Strings arbeitest. Bei einem Array kannst Du von 0 an vergleichen, bei einem String nicht. Grüße Klaus |
Re: Bubble-Sort
Leute, Leute: Da beherrscht ihr Quicksort im Schlaf, könnt Bayerbaumsuchverfahren, A*-Pathinfinding-Algorithmen und Knuth-Morris-Pratt-Grahpen rückwärts aufsagen, aber am guten alten Babelsort beisst man sich doch wirklich die Zähne aus. Ich habe auch stundenlang probiert, aufgegeben, meine Rente eingereicht und schließlich den Source auf www.sortieralgorithmen.de genommen und in mühevoller Kleinarbeit in Delphi übersetzt. Das Team hat wochenlang geschuftet und jedes Byte wurde von unserem 50-köpfigen Spezialistenteam handoptimiert und hochglanzpoliert.
Nun ist es aber soweit: Wir präsentieren - Babelsort 1.0!
Delphi-Quellcode:
Ach ja, das mit dem Vertauschen heisst 'Ringtauschverfahren'. Doch, es gibt einen Namen für sowas. Es heisst deshalb so, weil der Austausch ringförmig geht: h <-a <- b <- h.
procedure BubbleSort (Var s: String);
Var j,k, n: Integer; begin n := Length (s); for j:= n downto 2 do for k := 1 to j-1 do if s[k] > s[k+1] then vertausche(s[k], s[k+1]) end; |
Re: Bubble-Sort
jo wenn das so funktioniert muss dat wohl richtig sein :wink:
@netscanner wegen den zwei schleifen: du hast gesagt du verstehst das ganze ab der for-schleife nicht wirklich also hab ich dir geschrieben, wie das ganze funktionieren soll. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:52 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz