Probleme mit Sortieralgorithmus...
-
Hi,
ich schreibe gerade an einem C++ Programm & hänge seit ca. 1 Stunde an dem verwendeten Sortieralgorithmus...
Dieser soll eine Art Torjägertabelle sortieren...
Ich hoffe ihr könnt mir bei meinem selbsterstellten Sortieralgorithmus (ja hört sich schonmal schlimm an :p ) helfen, damit er endlich läuft...
Hier die Funktion:struct s_torjaeger { string torjaeger; string spieler; int tore; int uset; // TEMP (Wird errechnet...) int platz; }; struct s_sort { int index; int tore; }; void sortt(s_torjaeger t[], const int readlengtht, const int MID) { s_sort vsort[MID+1]; for(int zaehler3=1; zaehler3<=MID; zaehler3++) { vsort[zaehler3].tore=0; } for(int zaehler1=1; zaehler1<=readlengtht; zaehler1++) { for(int zaehler2=1; zaehler2<=readlengtht; zaehler2++) { if(t[zaehler2].platz==0) { if(vsort[zaehler1].tore<t[zaehler2].tore) { t[(vsort[zaehler1].index)].platz=0; vsort[zaehler1].index=zaehler2; vsort[zaehler1].tore=t[zaehler2].tore; t[zaehler2].platz=1; } } } } int temp=0; for(int zaehler4=1; zaehler4<=readlengtht; zaehler4++) { t[(vsort[zaehler4].index)].platz=zaehler4; } }Der Sortieralgorithmus soll die höchste Torzahl finden, die in ein array (vsort) mit index & toren gespeichert werden soll, dabei setzt er t[...].platz auf 1...
Am bevor die Tore verglichen werden, soll er prüfen ob das array t[...].platz auf 1 hat und überspringt dann das Tor vergleichen, weil dieser index schon auf ein platz zugewiesen wurde...Wenn ich das Programm starte & dann Torjäger eingebe in der Tor reihenfolge 2, 1 passiert nichts, aber wenn ich noch einen dritten torjäger hinzufüge & den mit 4 toren oder höher eingebe dann kommt "test2.exe hat ein Problem festgestellt und muss beendet werden."
Ich weiss echt nicht wodran es liegt und das ihr mir tipps geben könnt, wo vielleicht der fehler liegt mit begründung oder ohne (nur zum besseren verstehen)...
Vielen Dank fürs Lesen...
Ciao
LP-Fan
-
LP-Fan schrieb:
Ich hoffe ihr könnt mir bei meinem selbsterstellten Sortieralgorithmus (ja hört sich schonmal schlimm an :p ) helfen, damit er endlich läuft...
Erste Frage, bevor ich mir diesen anschaue:
1. Was ist daran C++? (Edit: vom string mal abgesehen)
2. Wenn C++: Selbstschreiben Vorgabe, oder dürfen auch die STL-Algorithmen verwendet werden?
-
1. Es ist C++...
Ich habe zum Beispiel letzte Woche struct gelernt...
2. Es gibt keine Vorgaben, hauptsache die Sortierung klappt...
Ich wollte nur mal einen eigenen machen & da ich jetzt nicht weiter komme und er nicht funktioniert, wollte ich auch die Schwachstellen & Fehler wissen zum lernen...
Denn man lernt aus Fehlern...
-
Wenn du lernen willst Suchalgorithmen selbst zu implementieren, dann kannst du dir auch einfache wie BubbleSort und schwierigere wie Merge- oder Heapsort einfach mal anschauen und versuchen nachzubasteln.
-
LP-Fan schrieb:
1. Es ist C++...
Wenn man vom string absieht sieht der Stil wie reines C aus, da du am Lernen bist, okay, nur sieht so eigentlich kein C++ Programm aus. Und auch das "s_" vor Strukturnamen ist mehr als ungewöhnlich (aber jeder den Stil den er mag, solange er konsistent bleibt).
LP-Fan schrieb:
2. Es gibt keine Vorgaben, hauptsache die Sortierung klappt...
Das heißt, man darf auch auf C++ Funktionalitäten beliebig zugreifen...
Ich bin mal spendabel und gebe dir einen C++ Crashkurs anhand deines Beispieles. Auch wenn ich hier nicht wirklich alles durchleuchte und dies nur mache um dir C++ Konstrukte einmal zu zeigen, ob sie hier sinnvoll sind oder nicht...
Wobei ich in einen weiteren Post mal tatsächlich deinen Sortieralgorithmus durchleuchte, nachdem ich es anders gelöst habe...
[Achtung: ungetestet Niedergeschrieben]Gehen wir Schrittweise vor, in jedem Schritt erkläre ich eine Sache mehr, ich werde aber kryptische Bezeichnungen auslassen, und ohne using namespace arbeiten (da man sich das eh abgewöhnen, oder zumindestens wissen muss wann man es NICHT verwenden sollte)...
=== 1. Konstruktoren ===
Wenn es wirklich C++ ist, würde ich mir gerne ein Leben leichter machen, und Konstruktoren einführen. Konstruktoren dienen dazu die Initialisierung einer Struktur oder Klasse durchzuführen.Ich nehme eine hierfür verkleinerte Klasse:
#include <string> struct Torjaeger { std::string torjaeger; std::string spieler; int tore; // Rest für Beispiel unterschlagen Torjaeger() : torjaeger(), spieler(), tore(0) {} Torjaeger( std::string const & torjaeger, std::string const & spieler, int tore = 0) : torjaeger(torjaeger), spieler(spieler), tore(tore) { } };So, was habe ich gemacht? Im wesentlichen siehst du zwei Sachen die genauso wie die Struktur heißen, sogenannte Konstruktoren. Stell sie dir einfach als Funktionen ohne Rückgabewert vor.
Der erste Konstruktor hat keine Parameter (Der sogenannte Standardkonstruktor), und initialisiert torjaeger, spieler mit einem Leerstring und tore mit einer 0. Der Aufruf erfolgt immer, wenn ein Objekt (Variable) dieser Struktur angelegt wird und keine weitere Angabe kommt:
Torjaeger t1; // <-- Hier erfolgt der Aufruf des StandardkonstruktorsDer zweite nimmt 3 Parameter an, wobei der Letzte mit einem Standardwert belegt wird, und daher nicht angegeben werden muß:
Torjaeger t2("a", "b", 2); // torjaeger="a", spieler="b", tore=2 Torjaeger t3("c", "d"); // torjaeger="c", spieler="d", tore=0 (Defaultbelegung)Soweit so gut...
=== 2. Vektoren ===
Vektoren kannst du dir im wesentlichen als dynamisch wachsende Arrays vorstellen, im ersten Moment mögen diese eine komplizierte Syntax als Arrays haben, aber die Vorteile überwiegen.#include <vector> //... int main() { // Aus Beispielsweise Torjaeger array[10]; // mache ich erstmal std::vector<Torjaeger> torjaeger; }Bei dem Vektor muss ich den Typ, den er Aufnimmt in eckigen Klammern angeben (Später wirst du wohl mal Templates kennen lernen, std::vector ist ein solches).
Wie fülle ich nun den Vektor, und warum habe ich die Konstruktoren eingeführt?
#include <vector> //... int main() { std::vector<Torjaeger> torjaeger; torjaeger.push_back(Torjaeger("Erwin", "Spieler 1", 2)); torjaeger.push_back(Torjaeger("Hans", "Spieler 1", 3)); torjaeger.push_back(Torjaeger("Egon", "Spieler 2", 1)); }Mittels push_back fügt man ein Element am Schluß des Vektors an, durch den Konstruktor muss ich das Objekt nicht mühsam vorher zusammenbasteln...
Zudem kann der Vektor noch einiges mehr als ein Array. Zum Beispiel "weiß" er seine Größe, kann einfach kopiert werden, wenn sein interner Speicher nicht aussreicht holt er neuen ohne das du dich darum kümmern musst...
So, ich fügen dies erstmal zusammen, lasse aber das sortierrelevante aus. Dabei reduziere ich das ganze ein wenig (nicht alle Membervariablen...)
#include <string> #include <vector> struct Torjaeger // Stark für das Beispiel reduziert { std::string torjaeger; int tore; int platz; // Wird berechnet Torjaeger() : torjaeger(), tore(0), platz(0) {} Torjaeger( std::string const & torjaeger, int tore) : torjaeger(torjaeger), tore(tore), platz(0) {} }; // <== Sortierrelevantes später int main() { std::vector<Torjaeger> torjaeger; torjaeger.push_back(Torjaeger("Erwin", 2)); torjaeger.push_back(Torjaeger("Hans", 3)); torjaeger.push_back(Torjaeger("Egon", 1)); torjaeger.push_back(Torjaeger("Werner", 0)); torjaeger.push_back(Torjaeger("Rudolf", 2)); // <== Sortierrelevantes später }=== 3. Sortierung Iteratoren ===
Ich werde hier mal etwas von deiner Frage abweichen, da ich das Wissen später nochmal aufgreife. Wie greift man auf einen Vektor zu?#include <iostream> //... Altbekanntes int main() { std::vector<Torjaeger> torjaeger; // <== Vector füllen // Erste Variante, über den Index (Das sollte dir vom Array bekannt sein. // Alle unsere Torjäger heißen mit Nachnamen Müller ;) [Häufiger Name halt] for(int index=0, size=torjaeger.size(); index<size; ++index) torjaeger[index].torjaeger += " Müller"; // // Zweite Variante, über einen Iterator // Geben wir mal die namen und Toranzahl nochmal aus for(std::vector<Torjaeger>::const_iterator it=torjaeger.begin(), end=torjaeger.end(); it!=end; ++it) std::cout << it->torjaeger << " (" << it->tore << ")" << std::endl; }Die zweite Variante sieht aber komplizierter aus... *einmal durchatmen* ...warum ist die zweite dennoch besser, und wie funktioniert das Ganze?
Fangen wir erstmal mit dem an, was Iteratoren eigentlich sind. Iteratoren kann man sich als Markierung eines Datensatzes in einem Container (das kann z.B. ein std::vector sein) vorstellen. Im einfachsten Fall einen Zeiger auf ein Element.
Nun ist es aber so, das nicht immer ein Array oder Vector das optimale ist, und nicht alle Container haben den Speicher linear aufgebaut. Das Bedeutet aber auch, das ein Indexzugriff, wenn die Elemente nicht mehr in direkter Reihenfolge liegen sehr langsam, wenn nicht gar unmöglich wäre (man müsste immer wieder bestimmen wo das Element wirklich liegt). Aus diesem Grund gibt es die Iteratoren.
Iteratoren versuchen eine möglichst allgemeingültige Behandlung aller Container zu ermöglichen, ohne das du als Anwender des Containers wissen musst wie die Elemente im Speicher liegen.Das sollte als minimale Erklärung dienen um das "was sind Iteratoren" zu erklären. Wie sie intern arbeiten, werde ich hier jetzt nicht ansprechen, wohl aber die Codezeilen und die dafür nötige Grundlagen schaffen.
1. const_iterator, iterator
Es gibt einmal den const_iterator und den iterator (und noch ein paar ungenannte mehr, diese Beiden sind nur für uns gerade die wichtigen). Der const_iterator erlaubt keine Manipulation der Datensätze auf die er verweist, der iterator hingegen schon. In dem Fall der Ausgabe ändern wir nichts, so das wir zum const_iterator greifen sollten.Statt wie im ersten Beispiel zwei int-Variablen in der Schleife zu definieren, lege ich hier zwei const_iterator'en an.
int index; // Variable "index", des Types int std::vector<Torjaeger>::const_iterator it; // Variable it, ein rein lesender // Iterator auf Elemente eines Containers des Types std::vector<Torjaeger> std::vector<Torjaeger>::iterator it2; // Variable it2, ein Iterator auf // Elemente eines Containers des Types std::vector<Torjaeger>, der sowohl // lesen wie auch schreiben erlaubt.2. begin(), end(), it!=end, ++it...
begin() liefert das Erste, end() - Achtung - das Element HINTER dem letzen Eintrag. mit ++it setzen wir ein iterator "it" um eine Position weiter; der Vergleich "it!=end" in der for-Schleife (Achtung: nicht kleiner, da wir nicht immer wissen wie der Speicher eines Containers aufgebaut ist) prüft daher, ob der iterator den Container noch nicht durchlaufen hat (Den ansonsten würde it==end, sprich dem Element HINTER dem letzten gültigen Eintrag sein).Warum ich das jetzt erkläre... nun, ich werde noch die Gelegenheit ergreifen einen anderen Container, der nicht linear aufgebaut ist zu erklären...
=== 4. Sortierung (Erste Annahmen) ===
Hier muß ich ein wenig raten was du vor hast. Wie es mir scheint, willst du ja nicht die Torjäger als solche Sortieren, sondern eine sortierte Torjägerliste haben. Du fasst in deinen Beispiel ja nie das Array sortierend an.Nur für eine Torjägerliste sehe ich ein anderes Problem. In meinen Beispiel oben wirst du eben dieses wiederfinden: Wie behandelst du Torjaeger mit Gleichstand?
So wie ich das Kenne müsste das Ergebnis doch wie folgt sein:
1. Hans (3 Tore)
2. Erwin, Rudolf (2 Tore)
4. Egon (1 Tor)
5. Werner (0 Tore)Um das abzubilden könnte ich deine zweite Struktur mal wie folgt anpassen:
#include <vector> struct TorjaegerPlazierung { std::vector<int> torjaegerPositionen; int tore; Torjaeger(int tore = 0) : torjaeger(), torjaegerPositionen(), tore(tore) {} };Mit dem Hintergrund, das für eine Toranzahl n mögliche Spieler existieren.
Aber irgendwie gefällt mir das nicht wirklich. Nenn mich ein Faultier, aber ich hätte gerne die Spieler direkt über die Toranzahl.
=== 5. Map ===
std::map ist ein weiterer Container. Der Sinn der Map ist ein anderer, als beim Vektor. Und zwar ist die Map eher mit einem Telefonbuch zu vergleichen. Über einen Schlüssel erhälst du einen Wert (z.B. über die Telefonnummer den Namen...).std::map<int, std::string> intStringMap;Dies wäre z.B. ein Container, in dem man über ein int-Wert ein String ermitteln kann. füllen könnte man diesen wie folgt:
std::map<int, std::string> intStringMap; intStringMap[8] = "a"; intStringMap[6] = "b";Jetzt hätte die Map zwei Einträge: [8, "a"] und [6, "b"]. Warum will ich diese map überhaupt? Hmm... erstens würde ich die Spieler gerne über die Tore ermitteln, und zweitens...
...die Map wird automatisch nach dem Schlüssel sortiert.
Habe ich schon erwähnt, das ich ein Faultier bin?
Aber noch ein Hinweis: Der Indexaufruf erzeugt wenn der Schlüssel nicht existiert einen Eintrag (Es gibt "find" um die Existenz zu prüfen, für uns aber unwichtig)
=== 6. Sortierung (Für Faule) ===
Okay... also mache ich mal folgendes. Nachdem ich den Vektor gefüllt habe, durchlaufe ich ihn und fülle die Map. Anschließend haben wir zu den Toren die Spieler...Dazu müssen wir aber erstmal die std::map deklarieren. Wir wissen, wir haben eine Toranzahl (int) die wir als Schlüssel verwenden. Soweit so gut. Pro Toranzahl haben wir aber wiederum n Spieler. Das n legt die Verwendung eines Vektors nahe, der Spieler soll erstmal wieder über den Index identifiziert werden.
Da wir über den Iteratorzugriff keinen Index haben, werden wir beim hierbei wieder auf den altbewährten Index zurückgreifen...
//... Altbekanntes int main() { std::vector<Torjaeger> torjaeger; // <== Vector füllen // Über Vektor die Map füllen. Die Toranzahl wird dabei als Schlüssel in der Map // verwendet, und der Index als Wert angehangen. std::map<int, std::vector<int> > torjaegerTore; for(int index=0, size=torjaeger.size(); index<size; ++index) torjaegerTore[torjaeger[index].tore].push_back(index); // <--- Schlüssel ---> -->Wert<-- // (anfügen zum Schlüssel) // <== Hier machen wir gleich weiter }So. nun haben wir eine Liste von Toren, inklusive Verweis auf die Torjäger-Indexe. Wobei die Liste ja nicht in (0..3 Tore), sondern gegen die Reihenfolge (3..0 Tore) benötigt wird.
Wir hatten ja schon die Iteratoren. Nun ist es nicht sinnvoll von "begin()" zum "end()" zu laufen. Das Gegenstück bilden die - ich nenne sie mal - Rückwärtsgerichteten Iteratoren (reverse iterator) "rbegin()" und "rend()"...
Bei der Map kommt noch eine Besonderheit bei den Iteratoren hinzu:
Der Iterator liefert ein "pair", ein Paar bestehend aus dem Schlüssel (it->first) und dem Wert (it->second).Und während wir durchlaufen wäre es nicht schlecht die Plätze in den Vektor zurück zu schreiben. Beginnend mit dem ersten Platz.
//... Altbekanntes int main() { // ... int aktuellerPlatz = 1; for(std::map<int, std::vector<int> >::const_iterator it=torjaegerTore.rbegin(), end=torjaegerTore.rend(); it!=end; ++it) { // Alle Spieler mit der Aktuellen Toranzahl auf dem gleichen Platz einordnen // Die zugehörigen Spieler bekommen wir über den Vektor der Spielerindexe, // den man über it->second bekommt... for(int index=0, size=it->second.size(); index<size; ++index) torjaeger[it->second[index]] = aktuellerPlatz; // Anschließend den aktuellen Platz um die Anzahl der Spieler erhöhen aktuellerPlatz += it->second.size(); } }So, nun verlagern wir mal die Platzermittlung (nicht Sortierung) in eine andere Funktion und schreiben mal alles zusammen:
=== 7. Zusammengeworfen ===
#include <string> #include <vector> #include <map> struct Torjaeger { std::string torjaeger; std::string spieler; int tore; Torjaeger() : torjaeger(), spieler(), tore(0) {} Torjaeger( std::string const & torjaeger, std::string const & spieler, int tore = 0) : torjaeger(torjaeger), spieler(spieler), tore(tore) { } }; std::map<int, std::vector<int> > ErstelleTorliste(std::vector<Torjaeger> const& torjaeger) { std::map<int, std::vector<int> > torjaegerTore; for(int index=0, size=torjaeger.size(); index<size; ++index) torjaegerTore[torjaeger[index].tore].push_back(index); } void Platzermittlung(std::vector<Torjaeger>& torjaeger) { std::map<int, std::vector<int> > torjaegerTore = ErstelleTorliste(torjaeger); int aktuellerPlatz = 1; for(std::map<int, std::vector<int> >::const_iterator it=torjaegerTore.rbegin(), end=torjaegerTore.rend(); it!=end; ++it) { for(int index=0, size=it->second.size(); index<size; ++index) torjaeger[it->second[index]] = aktuellerPlatz; aktuellerPlatz += it->second.size(); } } int main() { std::vector<Torjaeger> torjaeger; torjaeger.push_back(Torjaeger("Erwin", 2)); torjaeger.push_back(Torjaeger("Hans", 3)); torjaeger.push_back(Torjaeger("Egon", 1)); torjaeger.push_back(Torjaeger("Werner", 0)); torjaeger.push_back(Torjaeger("Rudolf", 2)); void Platzermittlung(torjaeger); }cu André
-
LP-Fan schrieb:
...
So, nach meiner zwar durchaus ernstgemeinten Einführung, aber nicht ernsthaften Problembetrachtung kommt die Analyse deines Codes...
Nicht alles erschließt sich hier intuitiv, und die Variablenbenennung ist auch nicht wirklich sprechend.
Ich weiß nicht was readlengtht und MID sein soll, und daher kann ich nur raten: readlengtht wird vermutlich die Größe des Arrays sein, bei MID bin ich mir nicht sicher was dies tun soll...
Aber grundlegende Dinge:
1. Arrays sind so groß, wie die Anzahl die du bei der Deklaration angibst.
Bei "s_sort vsort[MID+1];" legst du also ein Array mit MID+1 Elementen an.2. Die Indexe von Arrays beginnen bei 0, nicht bei 1
Dies ist nicht in C++ sinnvoll für Arrayzugriffe: "for(int zaehler3=1; ..."3. Weil man bei 0 mit dem Index beginnt, vergleicht man mit "<" gegen die Anzahl
Also: "for(int index=0; index<size; ++index)"4. [Ohne Erklärung]: ++index kann bei nicht Integralen Typen schneller als index++ sein. Daher nicht wundern, das ich mir grundsätzlich die Schreibweise ++index angewöht habe.
5. Niemals Variablen für etwas mißbrauchen, für das sie nicht gedacht sind. Programme sind auch ohne diesen Unsinn teilweise schon zu schwer zu lesen!
Also nicht den Platz in der Torjägerstruktur als Flag mißbrauchen während des Algorithmus, oder wenn es unbedingt sein muss: DOKUMENTIEREN!6. Variablen die in einer for-Schleife deklariert werden, sind nur für diese gültig (Falls nicht: Auf einen aktuellen Compiler wechseln, dann ist deiner schon stark veraltet, und wird noch andere Fehler haben). Daher musst du nicht jedesmal einen neuen Zählernamen aus den Fingern saugen, sondern nur wenn du verschachtelte for-Schleifen hast.
7. Dein Code ist so schwer zu analysieren das ich im Müden zustand derzeit aufgebe. Es ist leichter (Da du auch die Aufrufe kennst), diesen mal auf dem Blatt Papier mit 5 Datensätzen durchzuspielen.
8. Wähle sinnvolle Bezeichner. Weder t noch readlengtht noch MID können hier dem unbedarften Leser eine Bedeutung sagen, auch ist der Name sortt nicht sprechend, und eigentlich auch Falsch, da du nicht das tust was du sagst: Zu sortieren. Zumindestens nicht die Übergabe.
Dein Sinn ist doch eher die Platzermittlung wenn ich das richtig verstehe: Dann bitte auch so nennen.
Viel leichter wäre es einfach das Array mit std::sort und Angabe eines Sortierkriteriums zu sortieren, und dann die Platzierung über den (neuen) Index zu setzen...
cu André
P.S: Google mal nach Bubblesort
-
Hi Andre,
vielen Dank für deine Beiträge...
Ich habe in der Schule Informatik & wir machen gerade C++ (zumindest sagt uns das der Lehrer)...Für den Privaten Zweck wollte ich aus meinem Wissen eine FIFA 09 Tabelle+Torjäger erstellen...
Wo man Spieler hinzufügen kann, die mitmachen, matchergebnisse eintragen kann, torjäger hinzufügen & aktualisieren kann & halt eine sortierte Tabelle ausgeben kann...Wie ich sehe kann ich noch nicht viel in Sachen C oder C++, aber ich hoffe ich lerne noch viel, weil ich ziemlich gut darin bin (die Noten & der Informatiklehrer sagen dies zumindest)...
Mein komplettes Programm mit Daten in eine Datei schreiben & lesen usw. ist 510 Zeilen lang und das wollte ich euch (oder dir) nicht zumuten...^^Ich stehe noch ziemlich am Anfang von C/C++ programmierung...
Ich hatte schonmal den Bubblesort in der Hand, aber ich kam nicht drauf was ich da hätte ändern müssen um ihn für meine Bedürfnisse anzupassen...Das mit der Torjäger Tabelle war ja noch einfach, aber die Spieler Tabelle wo es nach Punkten, Tordiff & geschossen Toren geht, wird mir glaube ich das Genick brechen, wenn man das so sagen kann...
Deswegen habe ich hier etwas einfacheres gepostet um vielleicht dies dann eigenständig auf die Spieler Tabelle zu übertragen, aber durch die ganzen std::vector & solche Sachen bin ich erstmal verwirrt...^^Ich werde mal versuchen, durch die Dinge durchzusteigen was mir Andre (danke nochmal) gezeigt/geschrieben hat & versuchen das vielleicht selber aufzugreifen & für mein Programm zu benutzen, denn ich baue ungerne dinge in meine programme, die ich nicht verstehe...
VIELEN DANK FÜR EURE(DEINE) HILFE...
Ich melde mich, wenn ich wieder an eine Sackgasse komme...
Ciao Maurice