Quicksort bei Zeichenliste

Samarius · Hält's aus hier Beiträge: 3

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:

markieren

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; {of Function Zufallszahl}

Procedure LangeListe(Liste: TZListe);
var i:integer;
Begin;
i:=100;
repeat
  Liste.einfuegen(Zufallsbuchstabe);
  i:=i-1;
until i=0;

end; {of Procedure LangeListe}

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; {of Function Elementanzahl}


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 · Verfasst: 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

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

var ch1, ch2: char
...
begin
...
if (ord(ch1)<ord(ch2)) then ...

kannst du chars vergleichen.

Dragonclaw · Beiträge: 196 Windows Vista Delphi 7 Prof.

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

markieren

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 · Hält's aus hier Beiträge: 3

Erst mal vielen Dank für eure Antworten.

Ich nehme an, die Ermittlung des Pivotelements müsste dann so aussehen?

markieren

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

markieren

Delphi-Quelltext

1:	QuickSort(var Liste: TZListe);

schreibe?

Bergmann89 · Verfasst: 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

_________________
Ich weiß nicht viel, lern aber dafür umso schneller^^

Samarius · Hält's aus hier Beiträge: 3

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:

markieren

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
    // Wähle stets das mittlere Element als Pivotelement.
    Pivot := Liste[(ord(LoIndex) + ord(HiIndex)) div 2]; {E2149 Klasse besitzt keine Standardeigenschaft}

    // Stelle die Ordnung bzgl. des Pivotelements her.
    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;

    // Gegebenenfalls linke Teilliste sortieren.
    if ord(LoIndex) < Hi then QSort(ord(LoIndex), Hi);

    // Gegebenenfalls rechte Teilliste sortieren.
    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).

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme