Array nach unterschiedlichen Kriterien schnell sortieren

HeftCD · Verfasst: Di 20.06.06 14:00

ich habe Delphi 3

und möchte gerne einen 4 dimensionalen Array sortieren.
Also z.B. folgende Tabelle:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

_______Name____Datum_______Size_____Std
1      Jens    23.07.72    187       1   
2      Marc    04.01.75    175       1
3      Tina    12.02.74    167       2
4      Jan     27.06.71    195       1
5      Elke    08.12.72    170       2

Später sollen mal Arrays mit tausenden von Feldern sortiert werden.

ich habe jetzt schon versucht den Quicksort Algo einzubauen.
de.wikipedia.org/wik...sort#Delphi.2FPascal

hatte aber bisher noch keinen Erfolg damit [k.a. woran's liegt]
Liegt wohl an delphi 3 und fehlenden Functions...

hat jemand, eine Idee, wie man realisieren kann, daß wenn ich nach Geburtsdatum sortiere, die Namen und andern Daten weiterhin zuordbar bleiben?
also "Jan, 27.06.71 195 1" ganz oben, wenn ich aufsteigend nach Datum sortiere.
(bei Std. ist das egal, nur die anderen 3 muß ich sortieren können)
Und das soll später bei 1000 Datensätzen sehr schnell gehen.

Kennt Ihr eine Lösung?

Edit: Titel geändert

Narses · Verfasst: Di 20.06.06 14:51

Moin!

Zunächst mal: das ist kein 4-dimensionales Array, sondern 4 eindimensionale.

Um dir angemessen helfen zu können, hättest du mal etwas mehr Infos über die verwendeten Datenstrukturen angeben sollen.

Ich schlage jetzt einfach mal was vor:

markieren

Delphi-Quelltext

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

var
  Name: array[0..max] of String[30];
  Datum: array[0..max] of TDate;
  Size: array[0..max] of Integer;
  Std: array[0..max] of Integer;

  Index: array[0..max] of Integer;

begin
  for i := 0 to max do
    Index[i] := i;

Der Trick: du verwendest nicht den Index in die 4 Arrays direkt, sondern ein weiteres Index-Feld, eben Index[], um auf die tatsächlichen Daten zu zeigen. Du schlüsselst also einmal um, wobei die Vorbelegung von Index[] oben eine direkte Abbildung ist, also keine Sortierung aufweist.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

var
  i: Integer;

begin
  i := 5; // gewünscht: Zugriff auf das 5. Element
  i := Index[i]; // umschlüsseln
  ShowMessage(Name[i]); // zugehörigen Namen anzeigen

Wenn du jetzt sortieren möchtest, sortierst du das Feld Index[] anhand der Vergleichswerte, auf die der Index zeigt. Vorteil: du mußt nicht immer alle Daten im Speicher durch die Gegend schieben, sondern nur einen Zeiger (Index) darauf, das geht auch noch viel schneller.

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

crowley · Verfasst: Di 20.06.06 14:56

huhu..

ich würde prinzipiell mir einen record zusammenbasteln, der die verschiedenen "felder" enthält. dann einen array von diesem record machen und schwupps! kannst du den record nach beliebiger spalte sortieren... und die daten bleiben immer schön zusammen...

C.

HeftCD · Verfasst: Di 20.06.06 15:01

mhh, aber dann müßte ich ja einen Teil des Records in den Array kopieren und dabei jedes Mal die Reihenfolge der anderen Recordposition anpassen, wenn ich verschiebe, und das kostet doch Rechenzeit, oder?

crowley · Verfasst: Di 20.06.06 15:06

ähm... der array besteht nur aus den records und du sortierst dir den array

... sicher... es kostet etwas rechenzeit...

aber wie willst du ohne rechenzeit sortieren?

alias5000 · Verfasst: Di 20.06.06 15:07

Abgesehen davon, dass da vllcht eine DB nicht schlecht wäre, Warum nicht so:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

MyRecord = TRecord
  Name: string
  DAtum: string;
  {...}
end;

{...}

var Records: array of MyRecord;

{..}

Procedure Sort;
begin
QuickSort(Records, Kriterium);
end;

Gruß alias5000

_________________
Programmers never die, they just GOSUB without RETURN

HeftCD · Verfasst: Di 20.06.06 15:13

gerne so ,^^

aber ich weiß nicht, wie ich das mit dem Quicksort-Algo umsetzen soll.

u.a. Welche Parameter tatsächlich für die Function angegeben werden müssen.

Narses · Verfasst: Di 20.06.06 17:20

Moin!

Wir haben ja nun schon eine ganze Menge Vorschläge gemacht und alternative Ansätze aufgezählt.

Zeig doch mal deinen bisherigen Code, damit wir auch mal etwas von deinem Einsatz an der Sache sehen, ausserdem können wir dann besser auf deinen Ansatz eingehen.

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

HeftCD · Verfasst: Di 20.06.06 19:35

also das ist das , was ich bisher geschrieben habe.
Allerdings weiß ich nicht, wie ich den Array dann sortieren soll.

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:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

Type
MyRecord = Record
  Name: string;
  Datum: string;
  Size: integer;
  std: Byte;
end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

var Records: array[0..100] of MyRecord;

procedure quicksort(var a: array of integer; l, r: integer): forward;

procedure quicksort(var a: array of integer; l, r: integer);
var lpos, rpos, tmp, pivot: integer;
begin
  pivot := a[(l + r) div 2];
  lpos := l;
  rpos := r;

  while lpos <= rpos do
  begin
    while a[lpos] < pivot do inc(lpos);
    while a[rpos] > pivot do dec(rpos);
    if lpos <= rpos then
    begin
      tmp := a[lpos];
      a[lpos] := a[rpos];
      a[rpos] := tmp;
      inc(lpos);
      dec(rpos);
    end;
  end;
  if l < rpos then quicksort(a, l, rpos);
  if lpos < r then quicksort(a, lpos, r);
end;


procedure TForm1.Button1Click(Sender: TObject);
var
Index : array[0..100] of integer;
  i: Integer;
begin
records[0].Name := 'Jan';
records[0].Datum := '23.10.06';
ShowMessage (records[1].name);

 i := 0; // gewünscht: Zugriff auf das 5. Element
  i := Index[i]; // umschlüsseln
  ShowMessage(Name[i]); // zugehörigen Namen anzeigen
end;

end.

alzaimar · Verfasst: Di 20.06.06 19:49

Du schreibst Dir einfach eine Funktion 'MyCompare (a,b : TMyRecord)' die -1 liefert, wenn a 'kleiner als' b ist, 0, wenn beide identisch sind, und +1, wenn a'größer als' b ist. Da es sich bei a und b nicht um ordinale Typen handelt (also irgendwas, was man direkt vergleichen kann), musst Du das selbst definieren, z.B. so:

markieren

Delphi-Quelltext

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

Function MyCompare (a,b : TMyRecord) : Integer;
Begin
  If a.Feld1 < b.Feld1 Then Result := -1
  Else if a.Feld1 > b.Feld1 then Result := +1
  Else If a.Feld2 < b.Feld2 Then Result := -1
  Else if a.Feld2 > b.Feld2 then Result := +1
  Else If a.Feld3 < b.Feld3 Then Result := -1
  Else if a.Feld3 > b.Feld3 then Result := +1
  Else If a.Feld4 < b.Feld4 Then Result := -1
  Else if a.Feld4 > b.Feld4 then Result := +1
  Else ...
  else Result := 0
End;

Du definierst mit der Vergleichsfunktion eine totale Ordnung auf dein Array von Records, und damit lässt sich eben trefflich sortieren.

_________________
Na denn, dann. Bis dann, denn.

Narses · Verfasst: Di 20.06.06 20:01

Moin!

Probier das mal so:

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:
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;

interface

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

const
  MAX = 2;

type
  MyRecord = record
    Name: String;
    Datum: String;
    Size: Integer;
    std: Byte;
  end;

  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Zeigmir(const Was: Integer);
  private
    { Private-Deklarationen }
  public
    Records: array[0..MAX] of MyRecord;
    Index: array[0..MAX] of Integer;
    RecordCount: Integer;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Zeigmir(const Was: Integer);
  var
    i: Integer;
begin
  i := Index[Was]; // umschlüsseln
  ShowMessage('Was: '+IntToStr(Was)+' Index[Was]: '+IntToStr(i)+#13+
              Records[i].Name+#13+Records[i].Datum+#13+
              IntToStr(Records[i].Size)+#13+IntToStr(Records[i].std));
end;

procedure TForm1.Button1Click(Sender: TObject);
  var
    i,j: Integer;

  procedure SwapIndex(const Position: Integer);
    var
      temp: Integer;
  begin
    temp := Index[Position];
    Index[Position] := Index[Position+1];
    Index[Position+1] := temp;
  end;

begin
  // Werte vorbelegen
  Records[0].Name := 'Ich';
  Records[0].Datum := '01.01.2006';
  Records[0].Size := 123456;
  Records[0].std := 0;
  Records[1].Name := 'Du';
  Records[1].Datum := '02.01.2006';
  Records[1].Size := 654321;
  Records[1].std := 1;
  Records[2].Name := 'Er';
  Records[2].Datum := '03.01.2006';
  Records[2].Size := 615243;
  Records[2].std := 2;
  // Zuordnung: Identität
  for i := 0 to MAX do
    Index[i] := i;
  // Ausgabe
  ShowMessage('unsortiert');
  for i := 0 to MAX do
    Zeigmir(i);
  // Index nach Namen sortieren (BubbleSort)
  for j := MAX-1 downto 0 do
    for i := 0 to j do
      if (Records[Index[i]].Name > Records[Index[i+1]].Name) then
        SwapIndex(i);
  // Ausgabe
  ShowMessage('Nach Namen');
  for i := 0 to MAX do
    Zeigmir(i);
  // Index nach Size sortieren (BubbleSort)
  for j := MAX-1 downto 0 do
    for i := 0 to j do
      if (Records[Index[i]].Size > Records[Index[i+1]].Size) then
        SwapIndex(i);
  // Ausgabe
  ShowMessage('Nach Size');
  for i := 0 to MAX do
    Zeigmir(i);
end;

end.

Könntest du den Titel eventuell noch in etwas Sinnvolles ändern, wie z.B. "Array nach unterschiedlichen Kriterien schnell sortieren"? Danke.

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

HeftCD · Verfasst: Mi 21.06.06 14:01

erst mal Danke.

Ich habe nun versucht das ganze in den Quicksort algorithmus umzuschreiben.

phpfi.com/124925 << Code
(damit das hier übersichtlich bleibt, habe ich den Code extern gepostet - ist das in Ordnung?)

ich weiß leider nicht wie ich den Record da einbinden soll
und bin mir auch nicht sicher, ob nach dem Quicksort wirklich meine komplette Array-Tabelle umsortiert ist (und nicht nur 1 Element daraus)

Ìst das so richtig implementiert?

Narses · Verfasst: Mi 21.06.06 14:41

Moin!

Kannst du den Code (zumindest die entscheidenden Teile) trotzdem hier posten? Ist sonst historisch nicht schön, wenn das mal jemand später nachvollziehen möchte, fehlt u.U. dann der Code...

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

HeftCD · Verfasst: Mi 21.06.06 17:17

Klar, ich dachte nurr, daß der Thread dann sehr voll wird.

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:
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:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:

unit Unit1;

interface

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

const
  MAX = 100;

type
  MyRecord = record
    Name: string;
    Datum: string;
    Size: Integer;
    std: Byte;
  end;

  Type  TAMyrec = Array[0..Max] of MyRecord;

  TForm1 = class(TForm)
    Start_Btn: TButton;
    Close_Btn: TButton;
    Button1: TButton;
    procedure Start_BtnClick(Sender: TObject);
    procedure Ausgabe(const Was: Integer);
    procedure Close_BtnClick(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    Records: array[0..MAX] of MyRecord;
      Index: array[0..MAX] of Integer;
    RecordCount: Integer;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure QuickSort(var A: TAMyrec; lo, hi: integer);     // wie muß der Array heißen?
var i, j, h : integer;                                  //Records.name oder was?
 x: string;
begin

  i := lo;
  j := hi;
  x := a.name[( (lo + hi) div 2 )];
while i <= j do begin
  while a[i] < x do inc(i);
  while a[j] > x do dec(j);
  if (i <= j) then begin h := a[i];
    a[i] := a[j]; a[j] := h;
    inc(i); dec(j);
  end;
end;
if lo < j then QuickSort(a, lo, j);
if i < hi then QuickSort(a, i, hi);

end;


procedure TForm1.Ausgabe(const Was: Integer);
var
  i: Integer;
begin
  i := Index[Was]; // umschlüsseln
  ShowMessage('Was: ' + IntToStr(Was) + ' Index[Was]: ' + IntToStr(i) + #13 +
    Records[i].Name + #13 + Records[i].Datum + #13 +
    IntToStr(Records[i].Size) + #13 + IntToStr(Records[i].std));
end;

procedure TForm1.Start_BtnClick(Sender: TObject);
var
  i, j: Integer;

  procedure SwapIndex(const Position: Integer);
  var
    temp: Integer;
  begin
    temp := Index[Position];
    Index[Position] := Index[Position + 1];
    Index[Position + 1] := temp;
  end;

begin
  // Werte vorbelegen
  Records[0].Name := 'Ich';
  Records[0].Datum := '01.01.2006';
  Records[0].Size := 123456;
  Records[0].std := 0;
  Records[1].Name := 'Du';
  Records[1].Datum := '02.01.2006';
  Records[1].Size := 654321;
  Records[1].std := 1;
  Records[2].Name := 'Er';
  Records[2].Datum := '03.01.2006';
  Records[2].Size := 615243;
  Records[2].std := 2;
  // Zuordnung: Identität
  for i := 0 to MAX do
    Index[i] := i;
  // Ausgabe
  ShowMessage('unsortiert');
  for i := 0 to MAX do
    Ausgabe(i);
  // Index nach Namen sortieren (BubbleSort)
  for j := MAX - 1 downto 0 do
    for i := 0 to j do
      if (Records[Index[i]].Name > Records[Index[i + 1]].Name) then
        SwapIndex(i);
  // Ausgabe
  ShowMessage('Nach Namen');
  for i := 0 to MAX do
    Ausgabe(i);

  // Index nach Size sortieren (BubbleSort)
  for j := MAX - 1 downto 0 do
    for i := 0 to j do
      if (Records[Index[i]].Size > Records[Index[i + 1]].Size) then
        SwapIndex(i);
  // Ausgabe
  ShowMessage('Nach Size');
  for i := 0 to MAX do
    Ausgabe(i);
end;

procedure TForm1.Close_BtnClick(Sender: TObject);
begin
Close;
end;

procedure TForm1.Button1Click(Sender: TObject);
var xyz: MyRecords;
begin
QuickSort(xyz, 0, High(xyz)); // sortiert das ganze array
end;

end.

Narses · Verfasst: Mi 21.06.06 17:38

Moin!

HeftCD hat folgendes geschrieben:

Ich habe nun versucht das ganze in den Quicksort algorithmus umzuschreiben.

Wo denn? Irgendwie kann ich da praktisch keinerlei Anpassungen von dir finden, das ist doch bisher c&p...

HeftCD hat folgendes geschrieben:

Ist das so richtig implementiert?

Ähm, das ist ehrlichgesagt gar nicht implementiert.

Vielleicht solltest du erstmal Abstand von dem Quicksort nehmen und mit dem Index-Array und dem von mir implementierten BubbleSort arbeiten (was nebenbei gesagt gar nicht mal soo langsam ist, weil die Records im Speicher beim Sortieren nicht bewegt werden). Wenn deine Anwendung dann fertig ist und du siehst, ob du nicht vielleicht noch auf andere Probleme stößt, kannst du später problemlos den Sortieralgorithmus austauschen.

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

pascalsv · Verfasst: Di 29.08.06 16:47

Hallo zusammen,

ich gehe einen anderen Weg, der jedoch nicht funktioniert. Ich verstehe jedoch nicht, warum.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

Procedure SortArray(var aArray: array of TTrackArray; iColumn: integer);
var
  Str: string;
  Num: Integer;
  Check: Boolean;
begin
  repeat
    Check:=False;
    Num:=1;
    repeat
      if CompareStr(aArray[Num][iColumn], aArray[Num+1][iColumn])>0 then
      begin
        Str:=aArray[Num][iColumn];
        aArray[Num][iColumn]:=aArray[Num+1][iColumn];
        aArray[Num+1][iColumn]:=Str;
        Check:=True;
      end;
      Inc(Num);
    until(Num>length(aArray)-1);
  until(Check=False);
end;

Der Compiler meckert, das im CompareStr inkompatible Typen: Array und string stehen würden. Das verstehe ich nicht. Wenn mein Array als

markieren

Delphi-Quelltext

1:
2:

type
  TTrackArray = array of array[0..2] of string; // Index 0 = Artist; 1 = Titel; 2 = Path

definiert ist, müßte mein Weg doch grundsätzlich funzen, oder??

Danke für jede Hilfe!

Pascal

Martok · Verfasst: Di 29.08.06 23:45

pascalsv hat folgendes geschrieben:

markieren

Delphi-Quelltext

1:
2:
3:
4:

type
  TTrackArray = array of array[0..2] of string; // Index 0 = Artist; 1 = Titel; 2 = Path
....
Procedure SortArray(var aArray: array of TTrackArray; iColumn: integer);

Fällts dir auf? Der Parameter aArray ist also vom Typ:

markieren

Delphi-Quelltext

1:	array of array of array[0..2] of string;

Was wohl definitiv etwas viel array ist

Mit var aArray: TTrackArray; sollte es gehen.

//Martok

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

pascalsv · Verfasst: Do 31.08.06 09:04

Hallo Martok,

aber so wird doch ein multidimensionales Array aufgespant, oder nicht? Ich möchte ein Array haben, welches drei feste Spalten hat und sich beliebig von der Länge her anpassen läßt.

Oder??? :shock:

Pascal

Martok · Verfasst: Do 31.08.06 13:06

Im Prinzip ja, aber du hast ja TTrackArray als 2D-Array mit 3Spalten und Variabler Anzahl ans Spalten.

Jetzt ist aber dein Parameter ein 'array of TTrackArray', das Heisßt, du fügst nochmal eine Dimension hinzu, hast alos eine Variable Anzahl TTrackArrays.
Das wäre zum Beispiel so, als ob du mehrere Playlisten hast.

Daher als Parametertyp der Funktion nur TTrackArray verwenden, dann sollte es gehen ...*guckt nochmal in deinen Code*...Ja, stimmt.

//Martok

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme