Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Quicksort bei Zeichenliste
Samarius - Do 10.12.09 23:19
Titel: Quicksort bei Zeichenliste
Hallo, alle miteinander!
Wir behandeln im Informatikunterricht derzeit Sortieralgorithmen, um genau zu sein Quicksort. Unsere Aufgabe ist es, Quicksort bei einer Zeichenliste (char) anzuwenden. Als Lehrmaterial steht uns zwar das gesamte Internet zur Verfügung, allerdings finde ich nur Quellcodes für Integer-Arrays. Ich habe auch schon versucht, einen solchen Quellcode an die Liste anzupassen, hatte aber dabei keinen Erfolg.
Der Quelltext sieht wie folgt 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:
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:
| program Zeichenliste;
{$APPTYPE CONSOLE}
uses
SysUtils,
uTZListe ;
var Liste : TZListe;
Function Zufallsbuchstabe:char;
Begin;
Randomize;
Zufallsbuchstabe:=CHR(ROUND(Random(26)+65));
end;
Procedure LangeListe(Liste: TZListe);
var i:integer;
Begin;
i:=100;
repeat
Liste.einfuegen(Zufallsbuchstabe);
i:=i-1;
until i=0;
end;
Procedure Showliste(tmpListe :TZListe);
var abfragen : char;
Begin;
tmpListe.zumAnfang;
abfragen := tmpListe.abfragen;
WHILE abfragen <> tmpListe.undef Do Begin;
write(abfragen);
tmpListe.vor;
abfragen := tmpListe.abfragen;
end;
writeln;
end;
Function Elementanzahl(Liste:TZListe):integer;
Var i: integer;
Begin;
i:=0;
Liste.zumAnfang;
repeat
Liste.vor;
i:=i+1;
until Liste.abfragen=Liste.undef;
Elementanzahl:=i;
End;
Var x:char;
begin
Liste.initialisieren(Liste);
LangeListe(Liste);
Showliste(Liste);
readln(x);
writeln('Fertig!');
readln;
Liste.zerstoeren(Liste);
end. |
Kann mir jemand weiterhelfen?
Vielen Dank im Vorraus.
Boldar - Sa 12.12.09 12:53
Naja, du musst doch nur eine der Algoritmen für int werte nehmen und das array of integer in ein array of char umwandeln.
Mit
Delphi-Quelltext
1:
2:
3:
4:
5:
| var ch1, ch2: char
...
begin
...
if (ord(ch1)<ord(ch2)) then ... |
kannst du chars vergleichen.
Dragonclaw - Sa 12.12.09 13:02
du musst nur aufpassen, das Alles entweder lowercase oder uppercase ist, sonst wird M (ord(M) = 77) vor d (ord(d) = 100) sortiert. Also irgendwie sowas
Delphi-Quelltext
1:
2:
3:
4:
5:
| var ch1, ch2: char
...
begin
...
if (ord(ANSILowerCase(ch1)) < ord(ANSILowerCase(ch2)) ) then ... |
Moderiert von 
Narses: Code- durch Delphi-Tags ersetzt
Samarius - Sa 12.12.09 17:59
Erst mal vielen Dank für eure Antworten.
Ich nehme an, die Ermittlung des Pivotelements müsste dann so aussehen?
Delphi-Quelltext
1:
| Pivot := A[(ord(LoIndex) + ord(HiIndex)) div 2]; |
Boldar hat folgendes geschrieben  : |
| Naja, du musst doch nur eine der Algoritmen für int werte nehmen und das array of integer in ein array of char umwandeln. |
Wir sollen aber eine Liste und keinen Array sortieren... Oder reicht es, wenn ich am Anfang einfach
Delphi-Quelltext
1:
| QuickSort(var Liste: TZListe); |
schreibe?
Bergmann89 - So 13.12.09 00:51
Hey,
was du am ende deiner QuickSort-Prozedur übergibst ist ja dir überlassen, du muss es halt nur dementsprechend schreiben. Am bessten ist es wenn du den QuickSprt-Algo erstmal mit nem IntegerArray implementierst, dann kannst du ihn Testen und gucken ob du irgendwo Fehler hast. Und dann änderst du einfach die Parameter der Prozedur auf deine TZList ab und passt die vergleiche mit der Ord-Funktion an, das ist denke ich der einfachste Weg...
MfG Bergmann
Samarius - So 13.12.09 18:48
Danke noch mal. Leider kann ich erst morgen ausprobieren, ob es auch klappt (da mir die uTNListe-Datei aus den uses fehlt). Ich erstatte dann auch Bericht.
EDIT: Verdammt, ich kann es doch erst am Mittwoch ausprobieren...
EDIT2: Verdammt, ich kriege es nicht hin... "Klasse besitzt kine Standardeigenschaft" wird mir angezeigt... Ich habe auch gelesen, was das heißt, aber es hilft mir nicht weiter... So sieht es bisher aus, die Stelle, an der mir der Fehler angezeigt wird, habe ich mit einer Bemerkung versehen:
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:
| procedure QuickSort(var Liste: TZListe);
procedure QSort(LoIndex, HiIndex: Integer);
var
Lo, Hi: Integer;
Pivot: Integer;
Swap: Integer;
begin
Pivot := Liste[(ord(LoIndex) + ord(HiIndex)) div 2];
Lo := ord(LoIndex);
Hi := ord(HiIndex);
repeat
while Liste[Lo] < Pivot do Inc(Lo);
while Liste[Hi] > Pivot do Dec(Hi);
if Lo <= Hi then
begin
Swap := Liste[Lo];
Liste[Lo] := Liste[Hi];
Liste[Hi] := Swap;
Inc(Lo);
Dec(Hi);
end;
until Lo > Hi;
if ord(LoIndex) < Hi then QSort(ord(LoIndex), Hi);
if Lo < ord(HiIndex) then QSort(Lo, ord(HiIndex));
end;
begin
QSort(Low(Liste), High(Liste));
end; |
(Upper- und lowercase habe ich erst mal außen vor gelassen, erst mal wäre es schön, wenn es so funktionieren würde.)
EDIT3: Falls noch jemand eine Lösung haben sollte, ist es bei mir jetzt zu spät. Macht aber nichts, mein Informatiklehrer meinte er hätte sich schon gedacht, wo die Probleme auftreten werden. Wenn ich irgendwann mal an eine Lösung kommen sollte, poste ich sie hier (für den Fall, dass jemand mit dem selben Problem über diesen Eintrag stolpert).
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!