4 dimensionalen Array sortieren

[Coder]

ich habe Delphi 3

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

Delphi-Quellcode:

_______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.
http://de.wikipedia.org/wiki/Quicksort#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?

[r2c2]

Wenn ich dich richtig verstanden hab, dann brauchst du n stabilen Sortieralgorithmus. QuickSort ist instabil, hilft dir also wenig. Guck dich mal um; Auswahl gibts genug: www.sortieralgorithmen.de

mfg

Christian

P.S.: Du meinst nicht wirklich 4-Dimensional, oder? :gruebel:

[ste_ett]

Erstelle dir einen Record, der die vier (oder mehr) Attribute aufnehmen kann und erstelle dir dann einen Array dieses Record-Typen.
Diesen Array kannst du dann normal sortieren lassen. :)

P.S.
Du hast vier Werte keinen 4-dimenionalen Array. :)

[negaH]

Exakt, und schups wird QuickSort auch stabil. Hauptsache ALLE 4 Spalten werden in die Sortierung mit einbezogen.

Gruß Hagen

[bigg]

Hi,

der Ansatz ein "Array of Record" zu verwenden ist schon relativ gut, allerdings sollte man vermeiden alle Elemente des Arrays zu vertauschen. Beim Vertauschen müßte man theoretisch 3 mal "umkopieren" (und das für jedes Element in der Daten-Struktur) sofern man sich an "Bubblesort" orientiert. Solche Kopiervorgänge sind absolut unnötig und kosten nur unnötig Zeit. Auch soetwas mit anderen Sortieralgorithmen zu machen, ist Schwachsinn.

Wie verhindert man nun, das unnötige umkopieren?
Indem man Zeiger (Pointer) benutzt. Zeiger sind grob gesagt "Speicheradressen".
Man merkt sich also den Speicherort jedes Elements im Array und sortiert dann nur noch die Adressreihenfolge.

PS: Kein Kommentar zu weiteren^^... :mrgreen:

[Coder]

ja, gut, danke..
über das hin und her Kopieren in einen neuen Array habe ich mir auch schon Gedanken gemacht.
UNd verworfen, da wie gesagt Rechenzeit verloren geht.

Allerdings, wie kann ich das mit Pointern umsetzen?

also ich bin leider kein Delphi-Freak.
Ich kann nur rudimentäre Sachen programmieren.
Mit Pointern und Records kenn ich mich gar nicht aus.

Gibt es einen einfach Weg?

[Khabarakh]

Zitat:

Zitat von bigg

Hi,

der Ansatz ein "Array of Record" zu verwenden ist schon relativ gut, allerdings sollte man vermeiden alle Elemente des Arrays zu vertauschen. Beim Vertauschen müßte man theoretisch 3 mal "umkopieren" (und das für jedes Element in der Daten-Struktur) sofern man sich an "Bubblesort" orientiert. Solche Kopiervorgänge sind absolut unnötig und kosten nur unnötig Zeit. Auch soetwas mit anderen Sortieralgorithmen zu machen, ist Schwachsinn.

Wie verhindert man nun, das unnötige umkopieren?
Indem man Zeiger (Pointer) benutzt. Zeiger sind grob gesagt "Speicheradressen".
Man merkt sich also den Speicherort jedes Elements im Array und sortiert dann nur noch die Adressreihenfolge.

PS: Kein Kommentar zu weiteren^^... :mrgreen:

Denkst du wirklich, es macht einen so großen Unterschied, ob man nun 4 Byte oder 10 Byte (packed) herumkopiert? Zumal man mit Pointern ein zusätzliches Array benötigt, die Pointerliste.

@Coder: Records _sind_ der einfache Weg (und gehören IMO auf jeden Fall zu "rudimentärem Programmieren") ;) . Es schadet dir sicher nichts, dich mit ihnen bekannt zu machen.

[bigg]

Tutorial von Motzi zum Thema "Pointer":
http://www.manuel-poeter.de/index.php?site=tutorials

Was sind Records?:
http://www.dsdt.info/grundlagen/spra...datentypen.php


Ich würde es so machen:
- neuen Datentyp mit Hilfe von Records deklarieren (Der Datentyp beinhaltet 1*Name, 1*Datum, 2*Integer)
- anschließend ein Array des neuen Datentyps anlegen (um die Länge des Arrays mußt du dich kümmern)
- Array füllen, indem du auf die einzelnen Records zugreifst
- einen schnellen Sortieralgorithmus verwenden (Quicksort), der nun jedes Element mit jedem Element im Array vergleicht (Der Poinbter zeigt auf den Record, somit kommt man auch an die Daten: Name, Datum etc.)

Um Strings bzw. Zahlen zu vergleichen gibt es folgende Funktionen:
- CompareStr(): Integer;
- CompareText(): Integer;
- CompareValue(): Integer;
- ...

Alle 3 Funktionen liefern Zahlenwerte und mit diesen Zahlen kann man nun sortieren. Beim Vergleichen werden nun die Pointer (Reihenfolge) vertauscht, jedoch nicht die Daten auf denen der Pointer zeigt. Das spart Zeit und ist auch noch flexibel bzw. beliebig erweiterbar.

[r2c2]

*nochmal den 1. Post liest*
Ups, dann hab ich dich falsch verstanden; es ging also gar nicht um die Stabilität.

Zitat:

Zitat von negaH

Exakt, und schups wird QuickSort auch stabil. Hauptsache ALLE 4 Spalten werden in die Sortierung mit einbezogen.

Um Missverständnisse zu vermeiden. Hagen meint hier nicht Stabilität, sondern das, was die eigentliche Frage war(k.A. obs da n extra Wort gibt)...

mfg

Christian

[negaH]

Hi Christian,

ich meinte sehr wohl Stabilität ;) und bezog mich damit auf deine Aussage. Bei Quicksort ist es enorm wichtig das die Comparefunction (Vergleichoperation) immer eine eindeutige Sortierung erzeugt. Ist dies nicht der Fall so wird zb. die QuickSort Implementierung in der VCL (TList zb.) in einer Endloss-Schleife verenden.
Die eindeutige Vergleichoperation bezieht sich aber nur darauf das zb. nicht A > B und A <= B gleichzeitig gelten darf, oder zb. A > B und B > C und C > A.
QuickSort ist, je nach Implementierung, im Gegensatz zu anderen Verfahren, ziemlich anfällig für solche Kontradiktions in der Comparefunction, eben in-stabil !

Gruß Hagen