Sortieralgorithmen

[biby90]

hallo leute,
ja ich weiß die schon wieder :-)
heute muss ich eine funktion schreiben, die das vergleichen von 2 zeilen ersetzen soll (wenn ihr euch noch an den bubblesort von freitag erinnert)

Delphi-Quellcode:

unit sortieren;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
  function Sort(ASrcA, ASrcD: String): Integer;
  function CharToInt(AValue: Char): Integer;

    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  CharTable: array[0..25] of Char =
    ('A','B', 'C', 'D', 'E', 'F', 'G', 'H', 'I','J', 'K', 'L', 'M', 'N', 'O',
      'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z');



implementation


{$R *.dfm}



procedure TForm1.Button1Click(Sender: TObject);
var
  i, j : Integer; //Position
  Buffer: String; //speicher
begin
  for j := 0 to Memo1.lines.count -2 do
  begin
    for i := j+1 to Memo1.Lines.Count -1 do
    begin
      if Memo1.Lines[j] > Memo1.lines[i] then   //soll mit funktion Sort ausgetauschen werden
      begin
        Buffer := Memo1.lines[j];
        Memo1.Lines[j] := Memo1.Lines[i];
        Memo1.Lines[i] := Buffer;
      end;
    end;
  end;
end;

function TForm1.CharToInt(AValue: Char): Integer;
var
  i : Integer;
begin
  Result := -1;
  for i := 1 to length(CharTable) do
  begin
    if CharTable[i] = AValue then
    begin
      Result := i;
      Break;
    end;
  end;
end;

function TForm1.Sort(ASrcA, ASrcD: String): Integer;  // komme ab hier nicht weiter
var
  i: Integer;
  s: String;
begin
  Result := -1;
  for i := 1 to Length(CharTable) do

end;

end.

wenn ihr es euch mal ansehen könntet... über einen tipp würde ich mich freuen!

[DeddyH]

Hier kommt der Tipp *Trommelwirbel*: http://docwiki.embarcadero.com/VCL/d...istSortCompare
Schau Dir im Besonderen einmal die Rückgabewerte an.

[biby90]

theoretisch versteh ich es.... aber praktisch ist so eine Sache... ich probier mal rum.

[DeddyH]

Wenn es nur um das Vergleichen geht, würde ich die Funktion Compare nennen. Im ButtonClick könnte das dann später so aussehen:

Delphi-Quellcode:

for j := 0 to Memo1.lines.count -2 do
  begin
    for i := j+1 to Memo1.Lines.Count -1 do
    begin
      if Compare(Memo1.Lines[j], Memo1.Lines[i]) > 0 then

[biby90]

ich soll ja eine funktion erstellen die alle werte auf einmal vergleicht.

[DeddyH]

Das macht keinen Sinn. Oder soll die Funktion auch gleich das Tauschen und somit die komplette eigentliche Sortierung übernehmen?

[biby90]

nein eigentlich nur das vergleichen ich denke dass mein ausbilder mir bloß die funktionen näher bringen will.

[DeddyH]

Dann erklär doch einmal, was genau Deine Funktion vergleichen und vor allem, was sie zurückgeben soll (Minimum, Maximum oder was?).

[biby90]

also sie soll eben alle werte in einem Wort vergleichen und das Höchste auf eine Stelle höhersetzen... aber das soll ja im endeffekt nicht mit in die funktion. die funktion soll eben nur jeden einzelnen buchstaben eines worten mit den einzelnen buchstaben vom zweiten wort usw. vergleichen

[DeddyH]

Einen String kannst Du wie ein Array durchlaufen, um die einzelnen Buchstaben zu ermitteln. Und den ASCII-Code eines Buchstaben erhältst Du mit Ord().

[biby90]

also ich habe es jetzt so gemacht. wobei ich allerdings nicht weiß ob "sort" richtig ist aber das kläre ich gleich.
jetzt will ich ja in meiner procedure die eine Zeile mit Sort austauschen. aber wie mach ich das? der meckert immer!

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  i, j : Integer; //Position
  Buffer: String;
begin
  for j:=0 to Memo1.Lines.count -2 do
  begin
    for i:=j +1 to Memo1.Lines.Count -1 do
    begin
      if Memo1.Lines[j] > Memo1.Lines[i] then //tauschen mit funkction Sort
      begin
        Buffer:= Memo1.Lines[j];
        Memo1.Lines[j]:= Memo1.Lines[i];
        Memo1.Lines[i]:= Buffer;
      end;
    end;
  end;
end;

function TForm1.CharToInt(AValue: String): Integer;
var
  i: Integer;
begin
  Result := -1;

  for i := 1 to Length(CharTable) do
  begin
    if AValue = Chartable[i] then
    begin
      Result := i;
      Break;
    end;
  end;
end;

function TForm1.Sort(ASrcA, ASrcD: String): Integer;
var
  i: Integer;
begin
  Result := 0;
  for i:=1 to Length(ASrcD) do
  begin
    if ASrcA > ASrcD then
    begin
      Result:= i+1 ;
    end else
    begin
      Result:= i-1;
      CharToInt(ASrcA[i]);
      CharToInt(ASrcD[i]);
      Break;
    end;
  end;
end;

[DeddyH]

Wo meckert er? Wo wird Deine Funktion denn aufgerufen? Wozu dieses CharToInt statt Ord?

[biby90]

sollte ich so machen.... also wenn ich sort mit Memo1.lines tausche dann meckert er. also sie soll da aufgerufen werden wo ich den quelltext kommentiert habe.

[DeddyH]

Wer meckert? Der Compiler? Zeig doch mal den Quelltext, der da moniert wird, sonst kommen wir nicht weiter.

[S.pas.s]

Irgendwie scheint die Hilfe von DeddyH nicht sehr hilfreich zu sein.

wenn ich's richtig verstehe, soll die Zeile: "if Memo1.Lines[j] > Memo1.lines[i] then " dann z.B. lauten

"if StrCompare(Memo1.Lines[j], Memo1.lines[i]) > 1 then "

und StrCompare sollte dann z.B. so aussehen:

Delphi-Quellcode:

function TForm1.StrCompare(const s1, s2: String): Integer;
var
  j, minLen: Integer;
begin
  minLen := Length(s1);
  if Length(s2) < minLen then
    minLen := Length(s2);
  j := 1; result := 0;
  while (j <= minLen) and (result = 0) do
  begin
    if ord(s1[j]) < ord(s2[j]) then
      result := -1
    else
      if ord(s1[j]) > ord(s2[j]) then
        result := 1
      else
        result := 0;
    inc(j);
  end;
end;

Die Funktion liefert 0, falls beide Strings gleich sind, 1 falls s1 > s2 und -1 falls s1 < s2.

[DeddyH]

Vorkauen ist also hilfreicher (BTW: 'hal' und 'hallo' sind also gleich, kommt bei Dir zumindest raus)? Dann mach Du weiter, ich verabschiede mich.

[biby90]

also bin jetzt bis dahin

Delphi-Quellcode:

function TForm1.Sort(ASrcA, ASrcD: String): Integer;
var
  i: Integer;
  lResult: Integer;
begin
  Result := 0;
  for i:=1 to Length(ASrcD) do
  begin
    for lResult:= CharToInt(ASrcD[i]) to CharToInt(ASrcA[i]) do
      OutputDebugString( PChar(ASrcD[i] + ' = ' + IntToStr(lResult)) );
    begin
      if lResult > 0 then
      Result:= i+1;
    end;
    for lResult:= CharToInt(ASrcA[i]) to CharToInt(ASrcD[i]) do
      OutputDebugString( PChar(ASrcA[i] + ' = ' + IntToStr(lResult)) );
    begin
      if lResult < 0 then
      Result:= i-1;
    end;

er sortiert zwar aber nicht nach dem alphabet.

[DeddyH]

Du ermittelst doch Zahlenwerte aus den Buchstaben. Die kann man auch einfach von einander subtrahieren. Das macht allerdings auch nur solange Sinn, wie das Gesamtergebnis 0 ist, danach musst Du aus der Schleife raus, sonst überschreibst Du Dir das richtige Ergebnis ggf. mit einem falschen. Außerdem kann die Länge der Strings ja auch unterschiedlich sein, daher darf die Vergleichsschleife nur über die Länge des kürzeren laufen. Kommt da 0 bei heraus, ist der längere auch der größere.

[biby90]

prinzip verstanden... mal gucken ob es auch in der praxis klappr:lol:

[S.pas.s]

zu DeddyH:
Also ich lerne von anderer Leute code mehr als aus Büchern.

Damit (hal > hallo) oder (hal < hallo), muss man erst mal entscheiden, was sinnvoll wäre.
Eine Wahl wäre z.B. so:

Delphi-Quellcode:

function TForm1.StrCompare(s1, s2: String): Integer;
var
  j, minLen: Integer;
begin
  minLen := Length(s1);
  if Length(s2) < minLen then
    minLen := Length(s2);
  j := 1; result := 0;
  while (j <= minLen) and (result = 0) do
  begin
    if ord(s1[j]) < ord(s2[j]) then
      result := -1
    else
      if ord(s1[j]) > ord(s2[j]) then
        result := 1
      else
        result := 0;
    inc(j);
  end;
  if (result = 0) and (Length(s2) > minLen) then result := -1;
  if (result = 0) and (Length(s1) > minLen) then result :=  1;
end;

zu Biby90:
Du brauchst kein ChartoInt. Die Funktion ord macht das schon.
Zum Vergleichen musst Du synchron durch beide Strings laufen: (j = 1..minLen) bis einer von beiden zu Ende ist. Sobald ein Unterschied in der Zeichenfolge besteht, kann die Funktion beendet werden.

[DeddyH]

Wieso Bücher? Ich habe lediglich versucht, Hilfe zur Selbsthilfe zu geben, dabei lernt man nämlich noch mehr. Aber wenn der Compiler etwas moniert, ist es wenig hilfreich zu sagen "der meckert", ohne den Code dann zu zeigen.

[biby90]

naja ich brauche ja auch eigentlich keine Sort funktion... naja ich sollte die halt machen und jetzt eine, um das Memo1.lines > Memo1.lines blablabla zu ersetzen...
reiner lerneffekt.


nicht streiten.... :-(

[DeddyH]

Da nun bereits 2 mögliche Lösungen gepostet wurden, hier meine Umsetzung (die vielen Hilfsvariablen sollen dem Verständnis dienen):

Delphi-Quellcode:

function Min(Wert1, Wert2: integer): integer;
begin
  if Wert1 < Wert2 then
    Result := Wert1
  else
    Result := Wert2;
end;

function MyStrCompare(const Str1, Str2: string): integer;
var
  i, MaxLen, Laenge1, Laenge2, Wert1, Wert2: integer;
begin
  Result := 0;
  i := 1;
  Laenge1 := Length(Str1);
  Laenge2 := Length(Str2);
  MaxLen := Min(Laenge1, Laenge2);
  while (i <= MaxLen) and (Result = 0) do
    begin
      Wert1 := CharToInt(Str1[i]);
      Wert2 := CharToInt(Str2[i]);
      Result := Wert1 - Wert2;
      i := i + 1;
    end;
  if Result = 0 then
    Result := Laenge1 - Laenge2;
end;

Im ButtonClick dann

Delphi-Quellcode:

  for j:=0 to Memo1.Lines.count -2 do
  begin
    for i:=j +1 to Memo1.Lines.Count -1 do
    begin
      if MyStrCompare(Memo1.Lines[j], Memo1.Lines[i]) > 0 then 
        //tauschen

[biby90]

na das sieht doch schon eher nach dem aus was ich brauche. danke ich versuchs mal

[biby90]

hier das endprodukt... danke nochmal ihr seid die besten :thumb:

Delphi-Quellcode:

unit main;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    function Sort(ASrcA, ASrcD: String): Integer;
    function CharToInt(AValue: String): Integer;
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  CharTable: array[0..51] of String =
    ('A', 'a', 'B', 'b', 'C', 'c', 'D', 'd', 'E', 'e', 'F', 'f', 'G', 'g', 'H',
      'h','I', 'i', 'J', 'j', 'K', 'k', 'L', 'l', 'M', 'm', 'N', 'n', 'O', 'o',
      'P', 'p', 'Q', 'q', 'R', 'r', 'S', 's', 'T', 't', 'U', 'u', 'V', 'v',
      'W', 'w', 'X', 'x', 'Y', 'y', 'Z', 'z');



implementation


{$R *.dfm}



procedure TForm1.Button1Click(Sender: TObject);
var
  i, j : Integer; //Position
  Buffer: String;
begin
  for j:=0 to Memo1.Lines.count -2 do
  begin
    for i:=j +1 to Memo1.Lines.Count -1 do
    begin
      if Sort(Memo1.Lines[j], Memo1.Lines[i]) > 0 then
      begin
        Buffer:= Memo1.Lines[j];
        Memo1.Lines[j]:= Memo1.Lines[i];
        Memo1.Lines[i]:= Buffer;
      end;
    end;
  end;
end;

function TForm1.CharToInt(AValue: String): Integer;
var
  i: Integer;
begin
  Result := -1;

  for i := 1 to Length(CharTable) do
  begin
    if AValue = Chartable[i] then
    begin
      Result := i;
      Break;
    end;
  end;
end;

function TForm1.Sort(ASrcA, ASrcD: String): Integer;
var
  i, j: Integer;
  lResult: Integer;
begin
  Result := 0;

  for i:=1 to Length(ASrcD) do
  begin
    if CharToInt(ASrcA[i]) = CharToInt(ASrcD[i]) then
    begin
      Result := 0;
    end else
    begin
      if CharToInt(ASrcA[i]) < CharToInt(ASrcD[i]) then
      begin
        Result:= -1;
        Break;
      end else
      begin
        Result := +1;
        Break;
      end;
    end;
  end;
end;

end.

[DeddyH]

Und wenn ASrcA kürzer als ASrcD ist, kracht es u.U. in Deiner Sort-Methode, da Du aus dem Nirvana liest.

[biby90]

hö? verstehe gerade nur bahnhof.... es funktioniert auf jeden fall und das ist die hauptsache.
mein ausbilder findet es auch in ordnung

[DeddyH]

Dann ruf doch einmal

Delphi-Quellcode:

Sort('123', '12345')

auf.

[biby90]

hmm.... vorhin hatte es geklappt dass Baumhaus unter Baum stand und beim sortieren es eben getauscht hat

er machts immer noch genau so... nur nicht zahlen

[DeddyH]

Dann sortier nochmal oder ruf wie gezeigt die Funktion direkt auf.

[biby90]

versuch ich später habe jetzt eine neue Aufgabe bekommen... naja nach BubbleSort kommt jetzt halt ShellSort^^

[DeddyH]

Da wirst Du aber auch vergleichen müssen ;)

[biby90]

jop ich weiß.... bin grad dabei das zu verstehen und selber hinzukriegen....
nur diese beispiele im internet sind echt blöd!

[biby90]

kann hier jemand den fehler entdecken?

Delphi-Quellcode:

unit sortierenShell;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    procedure ShellSort(CharTable: String);

    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  CharTable: array[0..51] of String =
    ('A', 'a', 'B', 'b', 'C', 'c', 'D', 'd', 'E', 'e', 'F', 'f', 'G', 'g', 'H',
      'h','I', 'i', 'J', 'j', 'K', 'k', 'L', 'l', 'M', 'm', 'N', 'n', 'O', 'o',
      'P', 'p', 'Q', 'q', 'R', 'r', 'S', 's', 'T', 't', 'U', 'u', 'V', 'v',
      'W', 'w', 'X', 'x', 'Y', 'y', 'Z', 'z');

implementation

{$R *.dfm}


procedure TForm1.Button1Click(Sender: TObject);
var
  i, j: Integer;
begin
  ShellSort(Memo1.Lines[i]);
end;

procedure TForm1.ShellSort(CharTable: String);
var
  i, j, k: Integer;
  lBuffer: String;
begin
  i := Length(Memo1.Text) div 2;
  While i > 0 do
  begin
    j := k;
    if Memo1.Lines[j] > Memo1.Lines[j +i] then
    begin
      lBuffer := Memo1.Lines[j];
      Memo1.Lines[j] := Memo1.Lines[j +i];
      Memo1.Lines[j +i] := lBuffer;
    end else
    begin
      k := k +1;
      if k < Length(Memo1.Text) -i then
      begin
        i := i div 2;
        Break;
      end;
    end
  end;
end;

end.

[bernerbaer]

Zitat:

Zitat von biby90 (Beitrag 1117576)

kann hier jemand den fehler entdecken?

ja, sicher sehe ich Fehler ;-)
Ich finde Du solltest Deine Fragen konkreter formulieren. Wenn man sich selbst des Problems richtig bewusst ist, erkennt man oft selbst wo der Fehler liegt. Wo tritt ein Fehler auf? Ist es ein logischer Fehler oder ein Programmierfehler. Lässt sich der Code kompilieren, wenn nein welche Fehlermeldungen werden angegeben. Hast Du die Inhalte deiner Variablem mal angesehen bzw hast Du dich schon mit dem Debugging beschäftigt? Wenn nein, empfehle ich dir das Tutorial zum Debugging

[Bjoerk]

Delphi-Quellcode:

procedure TForm1.Button6Click(Sender: TObject);
// i undefiniert, j nicht benutzt
// ShellSort erwartet als Paramter eine CharTable

procedure TForm1.ShellSort(CharTable: String);
// CharTable wid nicht benutzt
// k undefiniert, j auch
// j ist k, weshalb j deklariert
// was soll diese procedure eigentlich machen ?

[himitsu]

Zitat:

Zitat von Bjoerk (Beitrag 1117686)

Delphi-Quellcode:

procedure TForm1.Button6Click(Sender: TObject);
// i undefiniert, j nicht benutzt
// ShellSort erwartet als Paramter eine CharTable

procedure TForm1.ShellSort(CharTable: String);
// CharTable wid nicht benutzt
// k undefiniert, j auch
// j ist k, weshalb j deklariert
// was soll diese procedure eigentlich machen ?

Delphi-Quellcode:

CharTable: array[0..51] of Char =  // warum war das "of String", wo es doch nur einzelne Chars sind?
    ('A', 'a', 'B', 'b', 'C', 'c', 'D', 'd', 'E', 'e', 'F', 'f', 'G', 'g', 'H',
      'h','I', 'i', 'J', 'j', 'K', 'k', 'L', 'l', 'M', 'm', 'N', 'n', 'O', 'o',
      'P', 'p', 'Q', 'q', 'R', 'r', 'S', 's', 'T', 't', 'U', 'u', 'V', 'v',
      'W', 'w', 'X', 'x', 'Y', 'y', 'Z', 'z');
// oder doch als String
CharTable: String = 'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz';
// oder als echte Konstante
CharTable = 'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz';

Bei Letzerem muß natürlich die Länge geprüft werden, zu beginn der Prozedur, bevor man auf die einzelnen Zeichen zugreift.

[DeddyH]

Das Length(Memo1.Text) verwirrt mich etwas. Müsste hier nicht die Zeilenanzahl stehen?

[himitsu]

ähhhh ... jupp

[biby90]

Zitat:

Müsste hier nicht die Zeilenanzahl stehen?

ja ich weiß^^ habs auch gesehen.
habe auch eine Schleife übersehn dir rein muss