Entwickler-Ecke :: Thema anzeigen - Quicksort von einer Liste

TN - Fr 11.02.11 16:26
Titel: Quicksort von einer Liste

Hallo, ich hab folgendes Problem. Wir haben in Informatik als Hausaufgabe, Wörter aus einer Liste mit Hilfe von quicksort zu sortieren. Den Quellcode für die Liste und einen quicksort eines arrays hab ich, jedoch weiß ich nicht wie ich die zusammenführen kann. Kann mir jemand helfen?

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:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:

unit Unit1;   //Sort1

interface

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

type
  TForm1 = class(TForm)
    SGListe: TStringGrid;
    Panel1: TPanel;
    EAnzahl: TEdit;
    Button1: TButton;
    BZufall: TButton;
    LZeitAuswahlsort: TLabel;
    procedure OnFormCreate(Sender: TObject);
    procedure BZufallClick(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure QuickSort(var A: array of Integer);

  private
    Anzahl:integer;
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.OnFormCreate(Sender: TObject);
begin
   SGListe.cells[0,0]:='    Nr';
   SGListe.Cells[1,0]:='              Wort';
   Anzahl:=0;
   ActiveControl:=EAnzahl;
   EAnzahl.text:='100';
end;

procedure TForm1.BZufallClick(Sender: TObject);
var i:integer;
begin
   Anzahl:=StrToIntDef(EAnzahl.text,0);
   If Anzahl>1 then begin
      SGListe.rowcount:=Anzahl+1;
      For i:=1 to Anzahl do begin
         SGListe.Cells[0,i]:=IntToStr(i);
         SGListe.cells[1,i]:=chr(random(26)+65)+ chr(random(26)+65)+chr(random(26)+65)+chr(random(26)+65)+chr(random(26)+65)+chr(random(26)+65);
      end;
   end else begin
      EAnzahl.text:='1000';
   end;
   LZeitAuswahlsort.Caption:='Zeit';
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  arr: array[0..100] of integer;
  I: Integer;
begin
  for I:=Low(arr) to High(arr) do
    arr[I]:=Random(High(Integer));

  QuickSort(arr);
            Application.ProcessMessages;
   end;


procedure TForm1.QuickSort(var A: array of Integer);

  procedure Quick_Sort(var A: array of Integer; iLo, iHi: Integer);
  var
    Lo, Hi, Mid, T: Integer;
  begin
    Lo := iLo;
    Hi := iHi;
    Mid := A[(Lo + Hi) div 2];
    repeat
      while A[Lo] < Mid do Inc(Lo);
      while A[Hi] > Mid do Dec(Hi);
      if Lo <= Hi then
      begin
        T := A[Lo];
        A[Lo] := A[Hi];
        A[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > iLo then Quick_Sort(A, iLo, Hi);
    if Lo < iHi then Quick_Sort(A, Lo, iHi);
  end;

begin
  Quick_Sort(A, Low(A), High(A));
end;


end.

Delphi-Laie - Fr 11.02.11 17:28

Quicksort von einer Liste? Brr....Laß mal die Präposition weg, dann wird es richtiges Deutsch (ansonsten ist es der "Vonotiv", eine sich immer weiter ausbreitende Sprachkrankheit).

Zu Deiner eigentlichen Frage: Wo wird denn das (un)sortierte Array ausgegeben? Ich sehe das nirgendwo. Wie willst Du den/das Quicksort denn sonst auf Korrektheit prüfen - mit einem Debugger?

Du rufst Quicksort mit dem Array ("arr") als Variablenparameter auf, insofern liegt die von Dir angezweifelte "Zusammenführung" doch schon vor!

Bergmann89 - Fr 11.02.11 18:01

Hey,

richtig er hat das Quicksort mit nem Array, er will es aber mit ner Liste. Leider ist die Liste keine Liste, sondern ein StringGrid. Nimm ma lieber ne TListBox (es sei denn du hast ne 2. Spalte, die ich hier jetzt nicht sehe). Dann kasnnst du die Items-Eigenschaft der ListBox an dein Quicksort übergeben. Items is so ne Art Array of String. Dann musst du in deinem Quicksort nur noch die nötigen Integer-Typen gegen String-Typen austauschen und zum vergleich CompareStr benutzen. Tauschen kannst du die dann über Items.Exchange(Index1, Index2: Integer). Fertig!

MfG Bergmann.

TN - Fr 11.02.11 20:56

Erstmal vielen Dank für eure Tipps.
Das Programm ist vom Lehrer vorgegeben, bis auf das Sortieren. Deshalb komme ich wohl nicht um den StrinGrid rum. Ist es denn auch damit möglich oder geht das jetzt gar nicht?

Delphi-Laie - Fr 11.02.11 21:16

TN hat folgendes geschrieben :

Die (eigentlichen) Elemente eines Stringgrids sind die in seinen Zellen enthaltenen Strings, die man sehr wohl hinsichtlich einer Größenreihenfolge definieren und vergleichen sowie mithin auch sortieren kann.

bummi - Sa 12.02.11 00:16

Vielleicht kannst Du hieraus Anregungen entnehmen

Bergmann89 - Sa 12.02.11 00:17

Hey,

natürlich ist das auch möglich, aber da solltest du die Daten vorher noch in eine TStringList kopieren. Und dann kannst du die TStringList an deine QuickSort-Methode übergeben. Das ganze solltest du deshalb machen, weil das Stringgrid ja ein visuelles Objekt ist, bedeutet der zeichnet das Ding jedesmal neu, wenn sich was in den Zellen ändert. Wenn du also in der Quicksort-Methode direkt mit dem StringGrid arbeitest, dann ist das ganze alles andere als Quick ;)
Als kleines Bsp: zu der TStringList:

Delphi-Quelltext

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

var 
  List: TStringList;
  i: Integer;

List := TStringList.Create;
try
  for i := 0 to SGListe.RowCount-1 do
    List.add(SGListe.Cells[0, i]);
  QuickSort(List);
finally
  List.Free;
end;

MfG Bergmann.