| Autor |
Beitrag |
IronBull
Hält's aus hier
Beiträge: 9
|
Verfasst: So 21.03.10 01:02
Hallo Leute, ich schreibe gerade an einer kleines Datenpaket in einer Datei und würde gerne wissen warum das Sortieren in die Hose geht.
Ich verwende Quicksort um die Datei rekursiv zu sortieren. Dazu verwende ich außerdem eine typisierte Datei in der records abgespeichert werden, die den Interpreten, Titel, Preis und Anzahl verkaufter Titel enthalten. Sprich das Datenpaket ist eine kleine CD Verwaltung.
Die Prozedur rufe ich nacher so | Zitat: | | quick(listendatei,1,filesize(listendatei)); |
Es läuft schief indem das Programm "Keine Rückmeldung" zeigt.
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:
| procedure quick(var f:FileT; li,re:integer);
var i, j:integer;
dummy,dummy2,mitte:KeyT;
a, b:char;
begin
i:=li;
j:=re;
seek(f, ((i+j) div 2));
read(f, mitte);
b:=mitte.interpret[0];
repeat
seek(f, i);
read(f, dummy);
a:=dummy.interpret[0];
while a < b do
inc(i);
seek(f, j);
read(f, dummy);
a:=dummy.interpret[0];
while a > b do
dec(j);
if i <= j then
begin
seek(f, i);
read(f, dummy);
seek(f, j);
read(f, dummy2);
write(f, dummy);
seek(f, i);
write(f, dummy2);
inc(i);
dec(j);
end;
until i > j;
if li<j then
quick(f, li, j);
if re>i then
quick(f, i, re);
end; |
Moderiert von  Christian S.: Code- durch Delphi-Tags ersetzt
|
|
Luckie
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: So 21.03.10 01:26
Während dein Programm den Code in der Schleife abarbeitet, kann es natürlich nicht mehr auf Nachrichten von Windows reagieren. Nach einer Bestimmten Zeit reagiert es dann für Windows nicht mehr. Du hast zwei Möglichkeiten, entweder du lagerst den Code in einen Thread aus, was die sauberere Möglichkeit ist oder du rufst in der Schleife Application.ProcessMessages auf, damit dein Fenster zwischendurch die Nachrichtenschlange abarbeitet.
Allerdings, kann ich mir nicht vorstellen, dass deine Schleife so lange arbeitet, dass Windows denkt, dein Programm würde nicht mehr reagieren. Kann es sein, dass die Abbruchbedingung nicht stimmt und du eine Endlosschleife hast?
|
|
SvenAbeln
Beiträge: 334
Erhaltene Danke: 3
|
Verfasst: So 21.03.10 03:13
Dein Quicksort stimmt nicht, du hast dort Endlosschleifen drin.
Falls a < b ist läuft deise Schleife ewig, da beide Variablen innerhalb der Schleife nicht verändert werden.
  Delphi-Quelltext
1:
2:
| while a < b do
inc(i); |
|
|
bole
Beiträge: 107
Erhaltene Danke: 15
win 10
|
Verfasst: So 21.03.10 04:14
Hallo
Soviel ich weiss ist Quick Sort nicht wirklich ideal als externes Sortierverfahren...
Bei internen Sortierverfahren sind alle Daten im Arbeitsspeicher, bei externen sind diese in einer Datei. Für externe Sorts ist Merge Sort zu bevorzugen.
Ich denke bei wenigen Datensätzen ist es performater diese komplett in den Speicher zu laden, zu sortieren und nachher die Datei zu ersetzten.
Siehe auch www.stefan-baur.de/cs.algo.sort.html
Gruss
Bole _________________ ein programm macht nicht das was du willst sondern was du schreibst!
|
|
IronBull 
Hält's aus hier
Beiträge: 9
|
Verfasst: So 21.03.10 10:35
@SvenAbeln
Super, danke für den Hinweis! Habe nun den Code umgeändert und versucht nach Anzahl zu sortieren. Hat astrein funktioniert !
Bleibt ein Problem. Hier unten ist die Stringvariante zu sehen. Bei dieser wird das erste Zeichen verglichen, allerdings funktioniert es nicht. Muss man evtl. wie in C andere Funktionen verwende wie "memcmp()" oder nicht?
Die Interpreten werden nicht geordnet !
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
| repeat
seek(f, i);
read(f, dummy);
while dummy.interpret[0] < mitte.interpret[0] do
begin
inc(i);
seek(f, i);
read(f, dummy);
end;
seek(f, j);
read(f, dummy);
while dummy.interpret[0] > mitte.interpret[0] do
begin
dec(j);
seek(f, j);
read(f, dummy);
end;
if i <= j then |
P.S.: @Bole danke für den Hinweis. Werde versuchen andere Methode noch einzubauen. Aber erstmal würde ich gerne eine Variante vollständig zum Laufen bringen.
cheers IronBull
|
|
alzaimar
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: So 21.03.10 11:11
Aus Gründen der Übersichtlichkeit würde ich eine Funktion implementieren, die einen bestimmten Datensatz liefert:
Delphi-Quelltext
1:
2:
3:
4:
5:
| Function RecordOfFile (aFile : TMyFileOfMyRecord; aRecordIndex : Integer) : TMyRecord;
Begin
Seek (aFile, aRecordindex);
Read (aFile, Result);
End; |
Anschließend noch eine Funktion, die zwei Datensätze miteinander vergleicht und -1,0 bzw. +1 liefert, je nach Vergleichsergebnis (kleiner, gleich, größer):
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| Function CompareRecords (a,b : TMyRecord) : Integer;
Begin
if a.interpret < b.interpret then
Result := -1
else
if a.Interpret > b.interpret then
Result := +1
else
Result := 0;
End; |
Und noch eine Funktion, die zwei Records miteinander vertauscht:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| Function ExchangeRecords (aFile : TMyFileOfRecord; aRecordIndex, theOtherRecordIndex : Integer);
Var
aRecord, theOtherRecord : TMyRecord;
Begin
aRecord := RecordOfFile (aFile, aRecordIndex);
theOtherRecord := RecordOfFile (aFile, theOtherRecordIndex);
seek (aFile, theOtherRecordIndex);
write (aFile, aRecord);
seek (aFile, aRecordIndex);
write (aFile, theOtherRecord);
End; |
Und nun Sortieren: 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:
| procedure QuickSort(aFile : TMyFileOfRecord; L, R: Integer);
var
I, J, P: Integer;
median : TMyREcord;
begin
repeat
I := L;
J := R;
P := (L + R) shr 1;
repeat
median := RecordOfFile (afile, P);
while CompareRecords (RecordOfFile (afile, I), median) < 0 do Inc(I);
while CompareRecords (RecordOfFile (afile, J), median) > 0 do Dec(J);
if I <= J then begin
ExchangeRecords(aRecord, I, J);
if P = I then
P := J
else if P = J then
P := I;
Inc(I);
Dec(J);
end;
until I > J;
if L < J then QuickSort(aFile, L, J);
L := I;
until I >= R;
end; |
Die Prozedur ist aus der Classes.Pas - Datei übernommen (TStringList.Quicksort). Ich habe nur die Aufrufe etwas angepasst.
Wie bereits erwäht, gibt es zum externen Sortieren geeignetere Verfahren. Aber am einfachsten ist es, die Datei einzulesen, In-Memory zu sortieren, und wieder abzuspeichern. Das ist natürlich sehr zeitaufwändig, wenn Du viele Einträge hast. Aber ich denke, für deine Sammlung sollte es reichen.
Das wohl beste Verfahren zum externen Sortieren ist übrigens 'MergeSort'. _________________ Na denn, dann. Bis dann, denn.
|
|
|
