Sortierprogramm

[cHillb3rT]

Ich hab die Aufgabe ein Sortierprogramm zu schreiben, das aus einer Datei die Daten ausliest und dann nach Vorname, Nachname und Alter sortiert.

In der Datei stehen die Begriffe so da:

VORNAME1,NACHNAME1,ALTER1

VORNAME2,NACHNAME2,ALTER2

Wie kann ich das gut lösen..... ich darf auch keine Strukturen verwenden, sondern soll dies alles mit Klassen und Funktionen lösen !

[Guybrush Threepwood]

Wie sieht denn dein Ansatz aus?

[cHillb3rT]

Als erstes musste ich mir bewusst werden, was das Programm machen soll.

Also:

-Datei öffnen

- 1. Person lesen

- 1. Person in Klasse speichern (neue Stringliste anlegen, Stringliste mit Werten füllen)

- 2. Person lesen

- 2. Person in Klasse speichern (neue Stringliste anlegen, Stringliste mit Werten füllen)

- Sortierung ????? *kA ob es hier schon sinnvoll ist*

-......

So hatte ich mir das in etwa vorgestellt.

Wie dann die Klasse aussehen wird, ist erstmal egal, denn das kommt danach.

Erstmal muss ja die Idee stehen !

[perdian]

- 2. Person lesen

- 2. Person in Klasse speichern

- Sortierung ????? *kA ob es hier schon sinnvoll ist*

Das kann man so machen. Wenn du allerdings ohnehin erst alle Personen einliest, ohne zwischendurch etwas damit zu machen, dann würde ich erst das Einlesen komplett durchführen und danach die Ergebnisliste sortieren. Dürfte ein deutlich besseres Laufzeitverhalten geben.

[cHillb3rT]

Das ist die Frage, denn die Sortierung erscheint mir auch so besser, aber ich bin mir net ganz sicher, weil mein Chef meinte, dass ein ganzer Durchlauf nicht so gut sei, weil man nicht weiß, wie groß die Datei am Ende sein wird.

Dennoch denk ich von der Logik her wie du..... naja wird sich goleich zeigen, was er so meint !

[perdian]

Das ist die Frage, denn die Sortierung erscheint mir auch so besser, aber ich bin mir net ganz sicher, weil mein Chef meinte, dass ein ganzer Durchlauf nicht so gut sei, weil man nicht weiß, wie groß die Datei am Ende sein wird.

Wie willst du es sonst machen?

Wenn du alle Datensätze der Reihe nach sortieren willst, musst du auch alle Datensätze zum Zeitpunkt des Sortierens kennen.

[cHillb3rT]

Chef meinte auch, dass es so sinnvoller sei

Aber nun muss ich erstmal ein Struktogramm zum Programm malen.... aber irgendwie will er auch noch was drin stehen haben, was genau mit der Klasse passiert.....

also kannste dir denken, was er haben will ?

[geloescht_Newlukai]

Du mußt Dir auch erst mal über die Klassen klar werden.

Normalerweise hast Du eine Klasse, die die Daten hält und eine Klasse, die ein Objekt der Datenhaltungsklasse bekommt und sortiert.

Also

• Daten in ein Objekt der Datenhaltungsklasse sichern
  
• Das Objekt an eine (statische) Funktion einer Sortierklasse übergeben
  

[cHillb3rT]

also wie ich die Daten einlese bin ich mir nun auch bewusst und eben hab ich mir überlegt, wie man die einzelnen Wörter sortieren kann.

Ich habs jetzt so gemacht, dass ich zwei for-Schleifen und eine if-Schleife nehmen werde.

In der ersten For-Schleife wird das derzeitige Element hochgezählt was man hat. Z.B. = A.

in der zweiten For-Schleife findet der Vergleich zwischen den A und den anderen eingelesenen Zeichen statt. Und in der If-Abfrage wird dann die Sortierung gemacht, nachdem man den Vergleich aus der zweiten For-Schleife ermittelt hat.

Also so:

for(i = 0; i<MaxInstanz; i++)

{

for (j = 0; j < Maxinstanz; j++)

{

Vergleich findet hier statt

if (Vergleich < 0)

{

}

else if(Vergeich > 0)

{

}

}

MaxInstanz++;

}

Ich denke damit kann ich das Sortierproblem einigermaßen lösen !

[perdian]

Ich denke damit kann ich das Sortierproblem einigermaßen lösen !

Ja, sieht nach einem schönen Bubblesort aus

Mehr auch hier:

http://www.sortieralgorithmen.de

[cHillb3rT]

hab ich gar net beachtet, dass dies ein Bubblesort sein kann

aber tHX 4 the info !

[cHillb3rT]

*Doppelpost*

Kann ich mit break; eigentlich auch mitten in der Forschleife schon abbrechen oder muss ich das anders machen, wenn ich schon nach 2 Vergleichen den richtigen Platz gefunden habe und eigentlich noch 3 Mal vergleichen kann ?

[perdian]

Kann ich mit break; eigentlich auch mitten in der Forschleife schon abbrechen [...] ?

Wieso probierst du es nicht einfach mal aus?

Dann hättest du schon in der halben Zeit, die du zum Schreiben dieses Beitrages gebruacht hast gemerkt, dass es nämlich genau so funktioniert, wie du es dir gedacht hast

[Bubble]

Da Du ja C++ verwendest, kannst Du einen Sortieralgorithmus der STL verwenden. Ist in Deinem Fall auf jeden Fall besser, als einen selbst gestrickten Bubblesort zu benutzen, der langsam ist.

Jeden Datensatz bringst Du in einer Instanz einer selbst definierten Klasse unter, die neben den notwendigen Feldern für die Einträge noch einen Vergleichsoperator (kleiner "<") implementiert. Die Objekte fügst Du dann einem Vektor Container für Deine Klassen hinzu (STL) und sortiest diese dann mit sort.

[cHillb3rT]

ja das geht sicherlich gut....

hab eben noch was bemerkt...

Also ich soll für jede Zeile, die in einer Datei vorhanden ist eine Instanz entwerfen, die eine Person darstellt.

Diese Instanz muss ich irgendwo ablegen. In einem Haufen zum Beispiel, wenn ich mich mal nicht sehr täusche.

Meine Frage ist aber nun:

- Wie sieht dieser Haufen aus ?

- Wie kann man ihn sortieren ?

- Wieviel kann man auf den Haufen draufpacken ?

- Gibt es schon eine vorgefertigte Haufenklasse in C++ ?

[cHillb3rT]

in haufen (heap) ist eine datenstruktur.

Ein bewerteter binärbaum wenn man so will.

Es gibt bestimmte eigenschaften die ein heap erfüllt.

Bei einem minimum heap ist jedes element in einer schicht kleiner als alle elemente in der darunterliegenden schicht. Das element ist also wurzel eines teilheaps. Das heisst weiter, dass die Wurzel das kleinste element des gesamten heaps ist.

[Bubble]

Also ich soll für jede Zeile, die in einer Datei vorhanden ist eine Instanz entwerfen, die eine Person darstellt.

Richtig. Muss ungefähr so aussehen:

class Person

{

public:

   std::string name;

   std::string vorname;

   // usw.

};

Dann brauchst Du noch eine Funktion

bool operator<(const Person& a, const Person& ;

Diese Instanz muss ich irgendwo ablegen. In einem Haufen zum Beispiel, wenn ich mich mal nicht sehr täusche.

Als "Haufen" käme das std::vector Template in Betracht. Instanzieren kannst Du es in der Form

std::vector<Person> meineListe;

Elemente (hier z.B. eine Klasseninstanz "meinePerson") fügst Du einfach hinzu mit: meineListe.push_back(meinePerson);

Meine Frage ist aber nun:

- Wie sieht dieser Haufen aus ?

std::vector

- Wie kann man ihn sortieren ?

std::sort(meineListe.begin(), meineListe.end());

(Vorher den Header <algorithm> einbinden)

- Wieviel kann man auf den Haufen draufpacken ?

Bis der adressierbare Speicher voll ist.

- Gibt es schon eine vorgefertigte Haufenklasse in C++ ?

s.o. (z.B. std::vector)

(Anmerkung: Alle Beispiele aus dem Kopf aufgeschrieben, wenn etwas nicht klappt C++ Doku lesen, es ist sicherlich so ähnlich ;-))

[Johannes Buchner]

Machs mit nem Bashscript

deine Zeilen schauen so aus:

VORNAME,NACHNAME,ALTER

Wenn du genau nach diesem Muster willst, mach einfach

sort datei.txt

sonst mit

cut -d, -f 2

erst herausholen, was du haben willst ...

Aber ich schätz mal Bash war nicht so gefragt