Problem mit Sortieralgorithmus

[fabiO]

Hallo,

Also ich habe ein Problem mit dem Quicksort Sortieralgorithmus.

Ich muss eine Liste von Namen, welche ich in einer Listbox darstelle, alphabetisch sortieren.
Jedoch muss ich dabei diesen Sortieralgorithmus verwenden:

Delphi-Quellcode:

PROCEDURE Quicksort ( Von , Bis : LongInt);

VAR   lz,rz   :       LongInt;
   t   :   Byte;      { Trennelement         }
   hilf   :   Byte;

BEGIN
  lz := Von;  rz := Bis;      { linker und rechter Zeiger   }
  t := F [ ( Von+Bis ) DIV 2 ];      { Trennelement aus Folgenmitte   }

  REPEAT

    WHILE F[lz] < t DO Inc(lz);      { linker Zeiger nach rechts   }
    WHILE t < F[rz] DO Dec(rz);      { rechter Zeiger nach links   }
    IF lz <= rz THEN         { falls keine šberschneidung...   }
      BEGIN
   hilf := F[lz];         { dann Austausch der Elemente   }
   F[lz] := F[rz];                 { die bez�glich dem Trennelement}
   F[rz] := hilf;         { auf der falschen Seite stehen   }
   Inc(lz);         { Anschlieáend die Zeiger eine   }
   Dec(rz);         { Position weiterr�cken      }
      END { Tauschen }

  UNTIL lz > rz;         { bis šberschneidung der Zeiger   }

  IF Von < rz THEN QuickSort ( Von , rz);  { linkes Teilfeld sortieren }
  IF lz < Bis THEN QuickSort ( lz, Bis );  { rechtes Teilfeld sortieren }

END;

Mein Problem ist nun, das ich nicht weiss inwiefern ich den Algorithmus ändern muss, damit ich damit auch String sortieren kann und nicht nur Integerwerte, oder wie ich die namen so einlesen kann das sie als Integerwert sortiert werden ( Das mit dem ASCII Code hab ich schon versucht, da komme ich nicht weiter).

Danke schonmal im Vorraus für eure Hilfe.

Ach ja hier noch der gesamte Code:

Delphi-Quellcode:

unit Unit1;

interface

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

CONST   Max = 1000000;

type
  Feld = ARRAY [ 1..Max] OF Byte;
  TForm1 = class(TForm)
    ListBox1: TListBox;
    Button1: TButton;
    Button2: TButton;
    Edit1: TEdit;
    Button3: TButton;
    StringGrid1: TStringGrid;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1 : TForm1;
  Namen : TStringList;
  F : Feld;
  bla : Array[0..9] of String;
  
implementation

{$R *.dfm}

{procedure anzeigen (grid : TStringGrid);
var x : Integer;
begin
For x := 0 to 7 do
  begin
    grid.Cells[x,0] := IntToStr(Werte[x,0]);
    grid.Cells[x,1] := IntToStr(Werte[x,1]);
  end;
end;}

PROCEDURE Quicksort ( Von , Bis : LongInt);

VAR   lz,rz   :       LongInt;
   t   :   Byte;      { Trennelement         }
   hilf   :   Byte;

BEGIN
  lz := Von;  rz := Bis;      { linker und rechter Zeiger   }
  t := F [ ( Von+Bis ) DIV 2 ];      { Trennelement aus Folgenmitte   }

  REPEAT

    WHILE F[lz] < t DO Inc(lz);      { linker Zeiger nach rechts   }
    WHILE t < F[rz] DO Dec(rz);      { rechter Zeiger nach links   }
    IF lz <= rz THEN         { falls keine šberschneidung...   }
      BEGIN
   hilf := F[lz];         { dann Austausch der Elemente   }
   F[lz] := F[rz];                 { die bez�glich dem Trennelement}
   F[rz] := hilf;         { auf der falschen Seite stehen   }
   Inc(lz);         { Anschlieáend die Zeiger eine   }
   Dec(rz);         { Position weiterr�cken      }
      END { Tauschen }

  UNTIL lz > rz;         { bis šberschneidung der Zeiger   }

  IF Von < rz THEN QuickSort ( Von , rz);  { linkes Teilfeld sortieren }
  IF lz < Bis THEN QuickSort ( lz, Bis );  { rechtes Teilfeld sortieren }

END;

procedure TForm1.FormCreate(Sender: TObject);
begin
  Namen := TStringlist.Create;

  Namen.Add('Anja');
  Namen.Add('Christoph');
  Namen.Add('Christian');
  Namen.Add('Daniel');
  Namen.Add('Dimitri');
  Namen.Add('Eldar');
  Namen.Add('Franz');
  Namen.Add('Fabio');
  Namen.Add('Peter');
  Namen.Add('Michi');
end;

procedure TForm1.Button1Click(Sender: TObject);
var x : Integer;
begin
  Randomize;
  for x := 1 to 10 do
    namen.Exchange(random(namen.Count), random(namen.Count));
  Listbox1.Items.Clear;
  ListBox1.Items.AddStrings(Namen);
end;

procedure TForm1.Button3Click(Sender: TObject);
var x : Integer;
begin
  Randomize;
  if Edit1.Text = '' then
    showmessage('Bitte geben sie einen Namen ein')
  else begin
    Namen.Add(Edit1.Text);
    for x := 1 to 10 do
      namen.Exchange(random(namen.Count), random(namen.Count));
    Listbox1.Items.Clear;
    ListBox1.Items.AddStrings(Namen);
  end;
end;

procedure TForm1.Button2Click(Sender: TObject);
var i : Integer;
begin
  For i := 0 to high(bla) do begin
    bla[i] := Namen.Strings[i];
    Stringgrid1.Cells[i,0] := (bla[i]);
  end;
  //quicksort(bla[0], bla[high(bla)]);
end;

end.

[RavenIV]

ich würde erst mal überall, wo ein integer-typ steht string hinmachen.
dann weiterschauen, ob der compiler motzt.
falls nein, dann mal mit dem debugger schauen, ob das sortieren auch klappt.

gruessle

[fabiO]

Also das mit dem umändern aller Integer-typen in Strings hab ich nich hinbekommen...

Ich hab dann ma versucht, mir die Anfangsbuchstaben aller Namen in ASCII Ausgeben zu lassen, was auch funktioniert.

Nur wenn ich diese Werte dann sortieren will, macht er nichts. (Ich hab die Werte vorher in ein Array geschrieben)

Ich denke das liegt daran, dass der Algorithmus keine Zahlenmengen sondern nur Zahlenreihen sortieren kann ( ich hoffe ich hab das jetzt richtig erfasst ).

d.h. wenn ich jetzt das Array bla mit den werten: 77 67 68 69 67 65 80 68 70 70

... wird da nix sortiert :(

Hier nochma mein geänderter Code:

Delphi-Quellcode:

  For i := 0 to high(bla) do begin
    bla[i] := Ord(Namen.Strings[i][1]);
    Stringgrid1.Cells[i,0] := IntToStr(bla[i]);
  end;

  quicksort(bla[0], bla[high(bla)]);

  For j := 0 to high(bla) do begin
    Stringgrid1.Cells[j,0] := IntToStr(bla[j]);
  end;

[marabu]

Hallo Fabio,

den QuickSort-Algorithmus hast du noch nicht so richtig verstanden - oder?

Es sind zwei lokale Variablen die du verändern musst. Wenn du ein array of byte sortieren willst, dann müssen die den Typ Byte haben und wenn du ein array of string (oder eine StringList) sortieren willst, dann müssen sie den Typ string haben. Ich hoffe der Spaß an deinen Hausaufgaben bleibt mit dieser Hilfestellung erhalten...

Grüße vom marabu

[fabiO]

huhu :)

Also da ich ja ein Array of String sortieren will, hab ich erstmal das Array Feld in String geändert (Feld = ARRAY [ 1..Max] OF String).
Danach musste ich ja noch die beiden lok. Variablen ändern, meiner meinung nach t und hilf...
aber damit der Algorithmus die Namen verarbeiten kann, muss ich doch auch die Parameter Von und Bis in String ändern, oder seh ich das grad wieder falsch?

Delphi-Quellcode:

PROCEDURE Quicksort ( Von , Bis : LongInt);

VAR   lz,rz   :       LongInt;
          t   :       String;            
       hilf   :       String;

BEGIN
    lz := Von;  rz := Bis;             
    t := F [ ( Von+Bis ) DIV 2 ];     

  REPEAT

    WHILE F[lz] < t DO Inc(lz);       
    WHILE t < F[rz] DO Dec(rz);         
    IF lz <= rz THEN                  
      BEGIN
        hilf := F[lz];                 
        F[lz] := F[rz];                
        F[rz] := hilf;               
        Inc(lz);                        
        Dec(rz);                    
      END                           

  UNTIL lz > rz;                 

  IF Von < rz THEN QuickSort ( Von , rz);
  IF lz < Bis THEN QuickSort ( lz, Bis );  

END;

Denn wenn ich eingebe quicksort(bla[0], bla[high(bla)]);
bekomm ich 'Incompatible Types: 'Integer' and 'String'

Wenn mir da noch einer weiterhelfen könnte wär ich ziemlich froh :)

[marabu]

Zitat:

Zitat von fabiO

damit der Algorithmus die Namen verarbeiten kann, muss ich doch auch die Parameter Von und Bis in String ändern

Die beiden Parameter nimmst du später zum indizieren deines array. Der Aufruf von QuickSort erfolgt dann mit den Array-Grenzen - nur welches Array willst du sortieren? Du hast deine Zeichenketten in der StringList Namen gespeichert und dort auch gemischt. Wenn du jetzt in der QuickSort-Routine F durch Namen ersetzt, sollte der Aufruf QuickSort(0, Pred(Namen.Count)) das gewünschte Ergebnis bringen. Schließlich ist die default property von TStringList ein indizierbares array...

Grüße vom marabu

[fabiO]

alles klar, ich habs verstanden :)

Nun funktioniert es, dankeschön :)

[marabu]

Wenn du mit Zeiger-Variablen sorgfältig umgehst, dann enthalten sie NIL, wenn sie noch nicht initialisiert wurden. Prüfen kannst du dann so:

Delphi-Quellcode:

begin
  if Assigned(Namen)
    then ShowMessage(Format('Namen enthält bereits %d Einträge', [Namen.Count]))
    else ShowMessage('Namen wurde noch nicht initialisiert');
end;

Wenn du Zeiger-Variablen während der Laufzeit deines Programms mehrfach initialisierst und freigibst, dann empfiehlt sich folgende Vorgehensweise:

Delphi-Quellcode:

begin
  FreeAndNil(Namen); 
end;

Namen.Free würde den Zeiger nicht wieder auf nil setzen und eine spätere Prüfung wäre schwierig bis unmöglich.

marabu

[fabiO]

yo ich habs nun einfach so gemacht, das ich die Namen Variable bei TForm.Create deklariere und so später die werte einfach hinzufüge... das klappt 1a...

Nur zwischendurch hatte ich noch das Problem, das er einige Namen nicht mitsortiert hat oder falsch sortiert hat, da der erste Buchstabe nicht uppercase war, deswegen musste ich das mit lowercase für alle namen umgehen ;)

Also danke nochmal für deine Hilfe :)