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

[r2c2]

Zitat:

Zitat von negaH

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 !

Danm hab ich dich entweder falsch verstanden oder ne andere Vorstellung von dem Begriff "Stabilität".
*nochmal in die Wikipedia guckt* http://de.wikipedia.org/wiki/Stabiles_Sortierverfahren
Jo, genau so, wie ichs im Kopf hatte:
Die Reihenfolge gleichwertiger Elemente wird nicht verändert. Das ist bei QuickSort aber nicht der Fall(im Normalfall jedenfalls). [wie gesagt, ich hatte die Frage falsch verstenden/nicht aufnmerksam genug gelesen]

Du bezieht Stabilität aber auf das Funktionieren des Algorithmus. Ohne eindeutige Vergleichsoperation ist (vergtleichsbasiertes) Sortieren IMHO unmöglich ==> Fehler bei der Implementierung der Compare-Funktion. QuickSort als Algo funktioniert aber trotzdem.

Oder hab ich dich falsch verstanden? :gruebel:

mfg

Christian

[negaH]

Nöö, ist absolut korrekt so ;)
Ich erwähnte dies nur weil ich denke das viele Programmierer so arbeiten wie ich.
Sie öffnen Classes.pas, kopieren sich die QuickSort Sourcen von TList, ändern sie an ihre Bedürfnisse, bauen ihre Compare Callbacks und wenn diese nicht saubere/stabile Vergleichsoperationen durchführt, wundern sie sich dann das ihr QuickSort eine Endloss-Sortierung durchführt. Sprich: ich wollte ein bischen meiner Erfahrungen mitgeben ;)

Gruß Hagen

[Coder]

habe ich nun auch versucht vom quicksort auf den Mergsort zu wechseln, da dieser stabiler ist und auch zur Sortierung von verketteten Listen geeignet.

http://de.wikipedia.org/wiki/MergeSort#Pascal

Allerdings scheint mein Programm da einen Fehler zu haben.


http://rapidshare.de/files/23793480/merges.zip.html (5 KB)

Fehler:

Delphi-Quellcode:

Im Projekt Mergesort.exe ist eine Exception der Klasse EConvertError aufgetreten. Meldung: ''' ist kein gültiger Integerwert'. Prozeß wurde angehalten. Fortfahren mit Einzelschritt oder Start.

in form1.hilf[x] := StrToInt(form1.Stringgrid1.cells[x,0]); //dynamische Array

x ist in dem Falle Null bzw. = 0.
weil der Algo sich schon ein paar mal aufgerufen hat.


kann sich jemand erklären, ob warum das so ist?
bzw. hat auch jemand ne Idee, wie ich die Zeilen in den Records damit sortiert bekomme (wenn Mergesort funktioniert)

Also ich bin momentan ratlos.

[r2c2]

Zitat:

Zitat von Coder

kann sich jemand erklären, ob warum das so ist?

Lies doch einfach die Fehlermeldung. An der ensprechenden Sstelle im StringGrid steht keine Zahl...

mfg

Christian

[Coder]

ok, gedacht hab ich mir das auch ...
aber wie kann das sein?

ich mein.... der algo ist doch so übernommen.
und es gibt doch maximal 10 Einträge.
wie kommt man dann auf Null?

Was kann ich denn abändern, damit das Ding durchläuft?

[r2c2]

Sorry, hab momentan meine Glasgugel verlegt. Mir fehlen n paar Infos:
- dein genauer Code
- der Inhalt deines StringGrids
- ...

Ach und noch ne Frage:
Hast du schon mal den Debugger bemüht? Was sagt der denn?

mfg

Christian

[Coder]

Code:

Sorry, hab momentan meine Glasgugel verlegt. Mir fehlen n paar Infos:
- dein genauer Code

http://rapidshare.de/files/23793480/merges.zip.html
(hatte das schon umseitig gepostet)

Code:

- der Inhalt deines StringGrids
- ...

wie meinste das?
Das is anfangs leer.

Code:

Ach und noch ne Frage:
Hast du schon mal den Debugger bemüht? Was sagt der denn?

ja, aber nix ungwöhnliches Entdeckt
also bin auch teilw mit F7 durchgesteppt.

[r2c2]

Zitat:

Zitat von Coder

Code:

Sorry, hab momentan meine Glasgugel verlegt. Mir fehlen n paar Infos:
- dein genauer Code

http://rapidshare.de/files/23793480/merges.zip.html
(hatte das schon umseitig gepostet)

Wens nicht so viel ist, kannst du sowas auch in den Beitrag schreiben. Die andere - komfortablere Möglichkeit als irgendwelche Freehoster - ist die Datei einfach an den Post anzuhängen...

Zitat:

Code:

- der Inhalt deines StringGrids
- ...

wie meinste das?
Das is anfangs leer.

Und ganau das ist das Problem. Was willst du sortieren, wenn du nix hast?

Zitat:

Code:

Ach und noch ne Frage:
Hast du schon mal den Debugger bemüht? Was sagt der denn?

ja, aber nix ungwöhnliches Entdeckt
also bin auch teilw mit F7 durchgesteppt.

Beim durchsteppen(und auch schon beim Angucken vom Code) müsste dir aufgefallen sein, dass du versuchst auf ne leere Zelle zuzugreifen. Und genau dabei krachts. Was für ne Zahl is bitte n Leerstring? Genau das versucht dir die Exception mitzuteilen...

mfg

Cheristian