Quicksort eines Datensatzes nach alphabet

[Sai]

hi leute^^

das ganze is in tp7.0

ich habe folgendes problem:



in meinem adressbuch programm werden profile eingegeben und dauerhaft
in ner externen datei gespeichert (assigne, rewrite, reset etc...)

nun soll mien programm die option bieten alle gespeicherten profile
alphabetisch auszugeben, sortiert nach name, alphabetisch halt


wie is das mit quicksort realisierbar?
meine probleme sind das ich die datei ja irgendwie mit links und rechts usw ins qsort bringen muss und das es wörter isnd und keine zahlen

ich frage hier, weil tp7 ja delphi sehr ähnlich ist und ihr vllt deshlab mir helfen könnt

[mr_emre_d]

verwende statt string char
mit char kannst du vergleichen!

vlt hilfts dir weiter...

:coder2:

MfG Emre

[DeddyH]

Oha, ich werde heute abend mal mein TP 7 "reaktivieren", vielleicht kann ich Dir dann helfen.

[RavenIV]

Du wirst die Adressen ja hoffentlich anständig organisiert haben?

Im besten Fall mit Records und besser noch in einer Liste von Records.
Nun kannst Du hier ja einen Sortieralgo drauf loslassen.

Soweit ich mich erinnern kann hat TP7 auch einen StringCompare (oder so ähnlich).
Damit kannst Du Record.Name vergleichen lassen und dann entsprechend sortieren.

[taaktaak]

Moin, Moin Sai.

Um eine zielgerichtete Antwort zu bekommen, sind einige weitere Informationen notwendig. Ausserdem ist der Titel m. E. etwas irreführend: Du willst doch nicht den Inhalt eines Datensatzes sortieren, sondern doch sicher den Inhalt der Datei - oder?

Wie ist der Datensatz gespeichert? Als Record (also file of) oder zeilenweise? Soll die Ausgabe (auf den Bildschirm?) sortiert werden oder die Datei?

Ich gehe im Augenblick davon aus, dass du eine Datei hast, die Datensätze darin in Form einzelner Records speichert sind und die Ausgabe auf dem Bildschirm nach Namen sortiert erfolgen soll.

Hierzu kannst du im Programm ein Record-Array definieren, die Datei in dieses Array einlesen, das Record-Array sortieren (z. B. mit Quicksort) und anschließend die Records des Arrays auf dem Bildschirm anzeigen lassen.

Wieviele Datensätze sind es denn? Übrigens, was meinst du denn mit...

Zitat:

die datei ja irgendwie mit links und rechts usw ins qsort bringen

???


Gruß Ralph

[Sai]

aha, das ging ja schnell^^

also die profile sind natürlich in record organsisiert und diese dann als reihe
die anazhl an profielen is nich festgelegt, je nachdem wieviel man eingibt, maximal 100 allerdings

ja, die sollen nach name sortiert werden, also in dem fall record.name

diese ganzen records werden dann mittels FILE OF (also assigne, write, etc...) gespeichert
das ganze soll nun so funktionieren, das wen ich im menü auswähle (alle profile anzeigen), die namen aller profile nacheinander ausgibt -> also will ich in erster linie die ausgabe sortieren

wenn das natürlich auch die orginal sortiert wärs besser, aber das isja noch schwerer
ich häng mal nen code teil an den ich fertig habe, wie ich mir da so gedacht hatte

Delphi-Quellcode:

PROCEDURE hilfsreihe;
VAR nummer : INTEGER;
BEGIN
     RESET(profile);
     nummer :=0; {=Nummer des ersten DS in Orig.-Datei}
     WHILE NOT EOF(profile) DO
           BEGIN
           READ(profile,datenbank);
           WITH (datenbank) DO
              BEGIN
              hilfsdaten[nummer].schl :=nam;
              hilfsdaten[nummer].nr   :=nummer;
              END;
           INC(nummer);
     END;
     r_index := nummer - 1;
     {writeln('Anazhl DS in DB;');
     writeln('Zaehlung beginnt mit 0');
     writeln(r_index);
     writeln; }
     GOTOXY(30,8);writeln('Weiter mit Enter!');
     writeln;
END;

PROCEDURE qsort (l,r : INTEGER);
VAR i,j,x,y       : INTEGER;
    sz            : tHILF;
BEGIN
     hilfsreihe;
     RESET(profile);
     i:=l;
     j:=r;
     x:=(l+r) DIV 2;
     REPEAT
           WHILE hilfsdaten[i] < x DO
           i:=i+1;
           WHILE x < hilfsdaten[j] DO
           j:=j-1;
           IF i<j THEN
           BEGIN
           y:=hilfsdaten[i];
           hilfsdaten[i] := hilfsdaten[j];
           hilfsdaten[j] := y;
           i:=i+1;
           j:=j-1;
           END;
     UNTIL i>j;
     IF l<j THEN
     qsort(l,j);
     IF i<r THEN
     qsort(i,r);
END;

     {FOR k := 0 TO (r_index - 1) DO
         BEGIN
           kleinstes := k;
           FOR l:=k+1 TO r_index DO
             IF hilfsdaten[l].schl < hilfsdaten[kleinstes].schl THEN
             kleinstes := l;
           sz := hilfsdaten[k];
           hilfsdaten[k] := hilfsdaten[kleinstes];
           hilfsdaten[kleinstes] := sz;
     END; }
END;

PROCEDURE hilfsdaten_speichern;
VAR k:INTEGER;
BEGIN
     ASSIGN(datenbanksort,'E:\pfsort.dat');
     REWRITE(datenbanksort);
     qsort(0..nummer);
     FOR k:=0 TO r_index DO
         write(datenbanksort,hilfsdaten[k]);
     CLOSE(datenbanksort);
END;

PROCEDURE sortdat_ausgeben;
VAR k,ke,dz:integer;
    test,test2:string;

BEGIN
     clrscr;
     kopf;
     hilfsdaten_speichern;
     textcolor(yellow);
     GOTOXY(25,6); write('Profile geordnet nach Name');
     GOTOXY(25,7); write('~~~~~~~~~~~~~~~~~~~~~~~~~~');
     textcolor(lightgray);
     writeln; writeln;
     RESET(profile);

     FOR k:=0 TO r_index DO
         dz:=0;
         BEGIN
         SEEK(profile,hilfsdaten[k].nr);
         READ(profile,datenbank);
         WITH (datenbank) DO
            test := datenbank.nam;
            test2:=datenbank.rasse;
            GOTOXY(22,11+(k*3));writeln(k+1,'.','Name: ':10,test:20);
            GOTOXY(24,12+(k*3));writeln('    Rasse: ':(10),test2:19);
            END;
         readln;{
         inc(dz);
         IF dz DIV 5 = 0 THEN
         BEGIN
         clrscr;
         ke:=k;
         kopf;
         GOTOXY(22,11+(ke/dz*3);writeln(k+1,'.','Name: ':(10),test:20);
         GOTOXY(24,12+(k/dz*3);writeln('    Rasse: ':(10),test2:19);
         END
         ELSE
         END;  }
END;

kurz zusammengefasst:

wenn das ausgeben im HP aufgerufen wird, wird zuerst ne hilfsreihe erzeugt aus der gespeicherten datei
danach kommt die qsort prozedur, wo ich keine ahnung habe wie ich die machen sollte dabei
darnter das in kommentarklammern is die "sortieren durch auswahl" lösung fürn notfall
dann wirds die sortierte hilfsreihe gespeichert
und diese ausgegeben


naja, hoffe ihr könnt mir helfen

@wer sich wundert, das da "rasse" steht, das programm geht um das spiel warcraft3, nur zum leichteren verständnis hab ich adressbuch geschrieben ;)

[taaktaak]

Moin, Moin Sai!
Ok, mit diesen Informationen kann sicherlich geholfen werden. Wenn du bis heute Nachmittag noch keine andere Hilfestellung erhalten hast, dann schau ich mir das mal in Ruhe an und werde mich wieder melden - habe tagsüber leider keine Zeit und im Büro auch kein TP7 zur Verfügung.
Gruß Ralph

[alzaimar]

Eigentlich steht doch da Alles :gruebel:
Im auskommentierten MinSort wird das Record-Feld 'schl' verglichen:

Delphi-Quellcode:

 IF hilfsdaten[l].schl < hilfsdaten[kleinstes].schl THEN

Im Quicksort dagegen der Record (was nicht funktioniert)

Delphi-Quellcode:

WHILE hilfsdaten[i] < x DO

Also ersetzt Du das durch

Delphi-Quellcode:

WHILE hilfsdaten[i].schl < x.schl DO

Fertig.

Es wäre allerdings eine gute Idee, eine Funktion 'RecordVergleich' zu schreiben, die das Ergebnis des Vergleiches zurückliefert, so in etwa:

Delphi-Quellcode:

Function RecordVergleich (a, b : TRecord) : Integer; // oder TVergleichsErgebnis = (veKleiner, veGleich, veGrößer)
Begin
       if a.Feld1 < b.Feld1 Then RecordVergleich := -1 // veKleiner
  else if a.Feld1 > b.Feld1 Then RecordVergleich := +1 // veGroeßer
  else if a.Feld2 < b.Feld2 Then RecordVergleich := -1 // veKleiner
  else if a.Feld2 > b.Feld2 Then RecordVergleich := +1 // veGroeßer
  else if a.Feld3 < b.Feld3 Then RecordVergleich := -1 // veKleiner
  else if a.Feld3 > b.Feld3 Then RecordVergleich := +1 // veGroeßer
...
  else RecordVergleich := 0
End;

Diese Funktion vergleicht zwei Records zuerst nach Feld1. Wenn die Records hier identisch sind, dann nach Feld2 und wenn sie da auch identisch sind, nach Feld3. Wenn sie da auch identisch sind, dann definieren wir die beiden Records als gleich (auch wenn in anderen Feldern unterschiedliche Werte stehen).

[Sai]

also hab nun das gemacht was alzaimar geschrieben hat, allerdings kommt bei genau der zeile der fehler
bei dem teil "x.schl" ungültige qualifizierung
lass ich das .schl weg kommt TYPEN nicht miteinander vereinbar

also geht immernoch nich :/

[taaktaak]

Hallo Sai!
Der Fehler ist logisch, es wird ja ein Record mit einem Integer-Wert verglichen - das kann natürlich nicht funktionieren. Ich bin auf dein Konzept nicht eingegangen, da ich die gesamte Vorgehensweise für ungünstig erachte. Wie schon angekündigt, ich mache heute Abend mal einen Alternativvorschlag zur Lösung.
Gruß Ralph

[taaktaak]

Hallo Sai!
Nun habe ich mal das alte Tp7 'rausgesucht. Beim Ausflug in die Vergangenheit habe ich mich dann ein wenig in alten Erinnerungen "festgelesen" - also hat es etwas länger gedauert. Dynamische Arrays hat es unter TP7 ja noch nicht gegeben, für die Speicherung der Datensätze hätte man damals also den Heap verwendet und eine verkettete Liste oder einen Baum angelegt. Das würde an dieser Stelle aber wohl zu weit gehen.

Wenn ich mich richtig erinnere, hast du unter TP7 nur 64 KBytes für alle Variablen zur Verfügung wenn du den Heap nicht benutzt. In Anbetracht der von dir genannten maximalen 100 Datensätze machen wir es am einfachsten so, wie man es eigentlich nicht machen sollte:

In der Unit deklarieren wir den DatenRecord, ein statisches Array um die Daten im RAM zu halten und einen Datensatz-Zähler...

Delphi-Quellcode:

type tDataRec = record of
                 Name  : String[aa]; // Länge eintragen!!
                 Rasse : String[bb]; // Länge eintragen!!
                 end;

var  DataArray : Array[0..99] of tDataRec;
     AnzData   : Integer;

Dann brauchen wir eine Procedur, um die Daten in das Array einzulesen...

Delphi-Quellcode:

procedure ReadData;
var f   : file of tDataRec;
    Idx : Integer;
begin
  Idx    :=0;
  AnzData:=0;
  assign(f,FileName);
  {$I-} reset(f); {$I+}
  if IOresult=0 then begin
    while not(eof(f)) do begin
      read(f,DataArray[Idx]);
      inc(Idx);
      end;
    close(f);
    AnzData:=Idx;
    end;
end;

Anschließend wird das Array sortiert. Habe dafür einen uralten, nicht rekursiven Quicksort gefunden und an unsere Aufgabenstellung angepasst, der unter TP7 funktionieren müsste...

Delphi-Quellcode:

procedure SortData;                            { Aufsteigend sortieren }
var s          : Array[1..20,1..2]of Integer;  { Typ : Record          }
    i,j,l,r,sp : Integer;
    x          : String[aa]; // Länge eintragen!!
    Hilf       : tDataRec;
begin
  sp:=1;
  s[1,1]:=0;
  s[1,2]:=AnzData-1;
  while sp>0 do begin
    l:=s[sp,1];
    r:=s[sp,2];
    dec(sp);
    while r>l do begin
      i:=l;
      j:=r;
      x:=DataArray[(r+l)div 2].Name;
      while i<=j do begin
        while (DataArray[i].Name<x) and (i<r) do inc(i);
        while (DataArray[j].Name>x) and (j>l) do dec(j);
        if i<=j then begin
          Hilf:=DataArray[i];
          DataArray[i]:=DataArray[j];
          DataArray[j]:=Hilf;
          inc(i);
          dec(j)
          end;
        end;
      if (r-i) < (j-l) then
        if l<j then begin inc(sp);s[sp,1]:=l;s[sp,2]:=j;l:=i end
               else l:=i
                       else
        if i<r then begin inc(sp);s[sp,1]:=i;s[sp,2]:=r;r:=j end
               else r:=j
      end
    end
end;

Nach einlesen und sortieren der Daten kannst du nun das Array auf dem Bildschirm ausgeben (Array von 0 bis AnzData-1 durchlaufen). Wenn du nach dem Einfügen von Datensätzen den Sort erneut aufrufst und die Daten speicherst, ist natürlich auch die Datei nach dem Namen sortiert.

Ich habe das obenstehende NICHT mit TP7 getestet - das ist nun dein Part. Eine Frage zum Schluss muss ich dann aber doch loswerden: Wieso machst du das mit Turbo Pascal?

Gruß Ralph

[Sai]

so, besten dnak für die hilfe, ich teste das morgen früh mal weil ich nun erstmal weg muss
aber danke^^

TP7 verwende ich, weil wir das von der schule aus müssen
wir lernen das da in info, deswegen
aber frag mich nich wieso
ich frag unseren lehrer immer mal danach, er sagt immer nur weils einfach is

wenn ich dann sage es is sinnlos, verwendet heute keiner mehr
wird das konsequent überhört^^

[taaktaak]

Na, wenn es so ist, diskutieren kann man mit Lehreren ja nicht so wirklich.
Gruß Ralph

[Sai]

so, hab das nun probiert und es schient zumindest vom syntax her zu stimmen
allerdings konnt ichs noch nich so richtig testen weil die ausgabe nich so hinhauen will
welche array soll ich da denn nun schlussendlich ausgeben, ich denke doch mal den DataArray oder ?oô

[taaktaak]

Korrekt! DataArray soll das EINZIGE Array sein, das du verwendest! Wenn du nicht klar kommst, wäre es wohl das Beste den kompletten Code durchzusehen. Kannst du mir auch als PN schicken. Ich kann mir gut vorstellen, dass einiges überflüssig geworden ist und gelöscht werden sollte.
Gruß Ralph