Sortieren von structs

Um sie ausgeben zu können: Pro Iteration baust du dir per sequentieller 
Suche ein Array im RAM aus den kleinsten N Einträgen auf. Dabei werden 
nur Einträge berücksichtigt, die grösser sind als der grösste vom 
vorigen Durchlauf.

klaus schrieb:

> Wie geht man vor wenn man diese Daten sortiert anzeigen möchte?

Musst du komplett durchsortieren?

> qsort um z.B. nach Namen zu sortieren.

qsort hilft dir dabei nicht

> Gibt es einen Lösungsansatz, denn man kann ja nicht alle Daten in den
> Speicher laden und dann sortieren, dazu reicht der Speicher nicht.

Dann musst du auf Methoden zurückgreifen, wie sie in den 60-er Jahren 
benutzt wurden um Daten zu sortieren, die auf Bändern liegen und nicht 
alle gemeinsam geladen werden können.

zb die Daten in mehrere 'Bänder' aufteilen.
Jedes Band für sich sortieren.
Danach jeweils 2 Bänder zu einem gemeinsamen neuen Band zusammenmischen. 
Das ganze wird solange wiederholt bis nur noch 1 einziges sortiertes 
Band übrig bleibt.

Das Mischen funktioniert so.
Stell dir vor du hättest 2 bereits sortierte Stapel mit Spielkarten.
Du hebts dann von jedem Stapel die erste Karte ab, die kleinere der 
beiden Karten legst du auf den Ausgangsstapel und hebst von demselben 
Stapel die nächste Karte ab. Wieder wird mit der Karte vom anderen 
Stapel verglichen und die kleinere auf den Ausgangsstapel gelegt. usw. 
usw.

Nur dass bei dir das eben keine Kartenstapel sind, sondern Files auf 
einer SD-Karte. Das halten der Daten im Speicher wird durch Lesen von 
einer Datei ersetzt.

(Und natürlich macht es keinen Sinn erst mal für jede Karte eine eigene 
Datei zu erzeugen. Daher teilt man die Komplettdaten erst mal in mehrere 
Haufen auf, sortiert die einzeln mit zb qsort, ehe dann das 
Zusammenmischen der einzelnen Haufen beginnt).

PS: man kann auch mehr als 2 Haufen in einem Durchgang zusammenmischen. 
Das Prinzip nach dem das funktioniert sollte augenfällig sein.

klaus schrieb:
> Wie geht man vor wenn man diese Daten sortiert anzeigen möchte?
> qsort um z.B. nach Namen zu sortieren.

Du kannst evtl. im RAM ein Feld anlegen, in dem Dateipositionen aller 
structs der Datei hinterlegt sind, also ähnlich wie Zeiger, nur halt auf 
den Dateianfang bezogen.
Mit einer passenden Vergleichsfunktion, die zwei solche Dateipositionen 
bekommt (bzw. die Zeiger darauf) und zurückliefert, welches der 
Dateielemente größer ist als das andere, kann man dieses Feld von 
Dateipositionen sortieren (z.B. mit qsort()).

Wenn du dann das sortierte Feld durchiterierst und an den so erhaltenen 
Positionen in die Datei schaust, hast du die sortierten Datei-structs.

Hat natürlich den Nachteil, daß man viel in der Datei lesen muß.

Was hast du erwartet? Zaubersprüche? Die Alternative zu anschliessendem 
aufwendigen Sortieren ist, gleich von Anfang an zusammen mit den 
sukzessive geschriebenen Daten einen Index aufzubauen. Auch da entsteht 
Aufwand, aber der verteilt sich.

klaus schrieb:
> Ich habe mal Eure Vorschläge getestet,

Welche? Es gab mehrere, allein Karl Heinz hat mehrere Varianten 
vorgeschlagen.
Am schnellsten wird die PC Variante sein, ok, nicht wenn man die Zeit 
für das umstecken der Karte mit berechnet :-)

Hei eines SD Karte sollte man vieleicht auch den Augenmerk auf möglichst 
wenig Schreibzugriffe legen, insofern ist ein Quicksort auf Dateiebene 
garantiert NICHT die schnellste Variante.

Ein ganz primitiver Ansatz:

*Datei A öffnen
*Kleinste(s) Element(e) bestimmen
*In Datei B kopieren
*Nächst kleinste(s) Element(e) bestimmen
*Kopieren
...
...
*Datei A löschen
*Datei B in A umbennen


Kommt mit sehr wenig RAM und relativ wenig Schreibzugriffen aus, 
skaliert aber nicht gut. Mit der Variante von A.K. ließe sich das 
kombinieren und beschleunigen.

Edit: Nicht ganz das gleiche, aber relativ ähnlich ist Selection Sort.
http://en.wikipedia.org/wiki/Selection_sort

Gruß
Reinhard