C# - Sortieren von ArrayList

Die Programmiersprache C# und Programmierung im .NET Framework/Mono
Antworten
Shrax
Beiträge: 87
Registriert: Sa Dez 27, 2008 8:08 pm

C# - Sortieren von ArrayList

Beitrag von Shrax » Di Jun 02, 2015 8:07 pm

Hallo,

ich habe eine ArrayList die Objekte enthält.
Nehmen wir als Beispiel ein Objekt welches einen Buchstaben darstellt.
Klasse: Buchstabe
Eigenschaften:
- Vorgänger : Buchstabe // Enthält ein Buchstaben-Objekt oder ist Null
- Nachfolger : Buchstabe // Enthält ein Buchstaben-Objekt oder ist Null
- Zeichen : String // Enthält das Zeichen das den Buchstaben darstellt

Die ArrayList enthält nun in zufälliger Reihenfolge Buchstaben.

Ich möchte eine Methode Sort() entwickeln, welche nun die ArrayList sortiert.

Frage:
Wie gehe ich in C# da am besten vor?

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: C# - Sortieren von ArrayList

Beitrag von Xin » Di Jun 02, 2015 11:52 pm

Shrax hat geschrieben:Ich möchte eine Methode Sort() entwickeln, welche nun die ArrayList sortiert.

Frage:
Wie gehe ich in C# da am besten vor?
Die Frage ist, welchen Algorithmus Du implementieren möchtest.

Du kannst zum Beispiel eine neue Liste zusammenstellen in dem Du aus deiner Quellliste das kleinste Element heraus suchst und in eine neue Liste einfügst. Das machst Du solange, bis die Quellliste leer ist.

Das ist eine Möglichkeit, aber es gibt eine ganze Reihe von Sortieralgorithmen. Die sind aber nicht auf C# beschränkt.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Shrax
Beiträge: 87
Registriert: Sa Dez 27, 2008 8:08 pm

Re: C# - Sortieren von ArrayList

Beitrag von Shrax » Mi Jun 03, 2015 9:18 am

Dankeschön für die Antwort Xin,


was mich interessieren würde ist ob C# hier bereits etwas anbietet.

Ich weiß, ich würde sicherlich mehr lernen wenn ich einen Sortieralgorithmus selbst implementiere, in diesem Fall möchte ich
aber wirklich rausfinden wie in C# hier die beste Vorgehensweise ist.

Ich habe die Schnitstellen IComparer gefunden, so wie ich mich hier jedoch eingelesen habe ist dieser für meine Problemstellung nicht der richtige Lösungsansatz,
um Objekte anhand ihrer Eigenschaften zu sortieren, wenn diese Eigenschaften auch Objekte sind. Denn im IComparer kann ich ja nicht vergleichen ob
Objekt A kleiner B ist, sondern ich muss suchen ob der Nachfolger von Objekt A in der Liste vorhanden ist.

Denn ich muss noch dazu sagen:
Mir geht es hier nicht um die Sortierung im Alphabet.
Es ist auch möglich dass das Programm mit den Daten "D ist Vorgänger von X" gefüttert wird, was X die Eigenschaft "D" als Vorgänger gibt.



Oder gibt es hierfür keine C# spezifische Lösung? Dann werde ich es trotzdem selbst mit einem Algorithmus versuchen.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: C# - Sortieren von ArrayList

Beitrag von Xin » Mi Jun 03, 2015 10:06 am

Shrax hat geschrieben:Ich habe die Schnitstellen IComparer gefunden, so wie ich mich hier jedoch eingelesen habe ist dieser für meine Problemstellung nicht der richtige Lösungsansatz,
um Objekte anhand ihrer Eigenschaften zu sortieren, wenn diese Eigenschaften auch Objekte sind. Denn im IComparer kann ich ja nicht vergleichen ob
Objekt A kleiner B ist, sondern ich muss suchen ob der Nachfolger von Objekt A in der Liste vorhanden ist.
Du kannst Dir Deinen eigenen Comparer schreiben und die Liste danach sortieren lassen.

https://msdn.microsoft.com/de-de/librar ... 10%29.aspx
Shrax hat geschrieben:Denn ich muss noch dazu sagen:
Mir geht es hier nicht um die Sortierung im Alphabet.
Es ist auch möglich dass das Programm mit den Daten "D ist Vorgänger von X" gefüttert wird, was X die Eigenschaft "D" als Vorgänger gibt.
Dann musst Du einen Comparer schreiben, der die entsprechenden Vergleiche durchführen kann und eben sagt, ob das eine Objekt vor, auf oder hinter dem anderen Objekt liegt.
Shrax hat geschrieben:Oder gibt es hierfür keine C# spezifische Lösung? Dann werde ich es trotzdem selbst mit einem Algorithmus versuchen.
Das Sortieren ist in C# enthalten. Den Vergleich musst Du selbst definieren.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Shrax
Beiträge: 87
Registriert: Sa Dez 27, 2008 8:08 pm

Re: C# - Sortieren von ArrayList

Beitrag von Shrax » Mi Jun 03, 2015 11:42 am

Hallo Xin,

danke für die Antwort.

Ich habe mich auch gleich dran gemacht einen Comparer zu schreiben. Nur jetzt sitze ich vor dem Problem, bei welchem ich schon gedacht habe das dies auftritt.

Ich habe folgeden Konstruktur für "Buchstabe":

Code: Alles auswählen

        public Buchstabe(string strBuchstabe, Buchstabe vorgaenger, Buchstabe nachfolger)
        {
            this.strBuchstabe = strBuchstabe;
            if(vorgaenger != null)
                this.vorgaenger = vorgaenger;
            if(nachfolger !=null)
                this.nachfolger = nachfolger;
        }
Ich habe Equals von Buchstabe so überschrieben:

Code: Alles auswählen

        public bool Equals(Buchstabe b)
        {
            if (b == null)
            {
                return false;
            }

            if (b.strBuchstabe == this.strBuchstabe)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
Ich habe folgende Liste:

Code: Alles auswählen

          
            List<Buchstabe> buchstabenListe = new List<Buchstabe>()
            {
                new Buchstabe("Y", new Buchstabe("X"), null),
                new Buchstabe("X", null, null),
                new Buchstabe("B", new Buchstabe("A"), new Buchstabe("C")),
                new Buchstabe("C"),
                new Buchstabe("A")
            };
Die Reihenfolge in der Liste ist also im Moment:
Y
X
B
C
A
Nach der Sortierung soll sie so sein:
X <- Weil "Y" seinen Vorgänger "X" kennt
Y <- Weil "Y" seinen Vorgänger "X" kennt
A <- Weil "B" seinen Vorgänger "A" kennt
B <- Weil "B" seinen Vorgänger "A" kennt
C <- Weil "B" seinen Nachfolger "C" kennt

Legetim wäre aber auch
A
B
C
X
Y
=> Ob die Kette "ABC" vor "XY" kommt, oder danach - kann das System noch nicht Wissen.

Zum Verständnis:
Das Progamm soll im Endzustand von der Console
neue Buchstaben bekommen. Diese Buchstaben können dazu
einen Vorgänger oder Nachfolger haben.
Wurden ein paar Buchstaben eingegeben "Sortiert" das Programm
anhand der eingegbenen Buchstaben die Liste.
Dadurch "lernt" das Programm quasi durch die Buchstaben und deren Verknüpfungen
wie die richtige Reihenfolge des Alphabets ist.

Das ganze soll in minimaler Form einen Lernprozess abbilden.
Lehrer(Eingabe) -> B kommt nach A;
Lehrer(Eingabe) -> B kommt vor C;
Schüler (Programm) erkennt: ABC gehört zusammen.


Mein Problem:
Das Ergebnis meines Programmes ist derzeit:
Y
X
B
C
A

Das Problem liegt soweit ich sehe daran, dass der Comparer nur "gleich", "größer" oder "kleiner" kennt.
Man müsste dem Comparer noch die Information geben, dass es Objekte gibt die nicht Sortierbar sind.
Diese müssten dann einfach an den Anfang oder das Ende der Liste geschoben werden. (Ist faktisch egal ob vorne oder hinten,
Hauptsache sie bleiben in der Liste. Denn wenn das Programm neue "informationen" bekommt, ist es evtl. möglich diese
zu sortieren.


Wie sage ich das dem Comparer? Ich dachte ich gebe dann einfach "0" für "gleich" zurück, aber
das haut anscheinend nicht hin.

Code: Alles auswählen

    class BuchstabenComparer : IComparer<Buchstabe>
    {
        public int Compare(Buchstabe x, Buchstabe y)
        {
            int result;
            Buchstabe b1 = x;
            Buchstabe b2 = y;
            if(b2.Equals(b1.nachfolger))
            {
                result = 1;
            }
            else if (b2.Equals(b1.vorgaenger))
            {
                result = -1;
            }
            else
            {
                result = 0;
            }


            return result;
        }
    }

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: C# - Sortieren von ArrayList

Beitrag von Xin » Mi Jun 03, 2015 1:07 pm

Shrax hat geschrieben:Ich habe mich auch gleich dran gemacht einen Comparer zu schreiben. Nur jetzt sitze ich vor dem Problem, bei welchem ich schon gedacht habe das dies auftritt.
Nämlich?
Shrax hat geschrieben: Ich habe folgeden Konstruktur für "Buchstabe":

Code: Alles auswählen

        public Buchstabe(string strBuchstabe, Buchstabe vorgaenger, Buchstabe nachfolger)
        {
            this.strBuchstabe = strBuchstabe;
            if(vorgaenger != null)
                this.vorgaenger = vorgaenger;
            if(nachfolger !=null)
                this.nachfolger = nachfolger;
        }
Ein wirklich wunderschönes Beispiel, warum man Programmieren bitte nicht in Java oder C# lernen sollte, weil man sich ansonsten auf kurz oder lang, mächte auf die Kauleiste legt. :-)
Shrax hat geschrieben: Ich habe Equals von Buchstabe so überschrieben:

Code: Alles auswählen

        public bool Equals(Buchstabe b)
        {
            if (b == null)
            {
                return false;
            }

            if (b.strBuchstabe == this.strBuchstabe)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
Heute wird übrigens niemand mehr nach Lines of Code bezahlt.

Code: Alles auswählen

        public bool Equals(Buchstabe b)
        {
            return b != null && b.strBuchstabe == strBuchstabe;
        }
Shrax hat geschrieben: Ich habe folgende Liste:

Code: Alles auswählen

          
            List<Buchstabe> buchstabenListe = new List<Buchstabe>()
            {
                new Buchstabe("Y", new Buchstabe("X"), null),
                new Buchstabe("X", null, null),
                new Buchstabe("B", new Buchstabe("A"), new Buchstabe("C")),
                new Buchstabe("C"),
                new Buchstabe("A")
            };
Wie funktioniert denn new Buchstabe("C")?!
Shrax hat geschrieben: Die Reihenfolge in der Liste ist also im Moment:
Y
X
B
C
A
Nach der Sortierung soll sie so sein:
X <- Weil "Y" seinen Vorgänger "X" kennt
Y <- Weil "Y" seinen Vorgänger "X" kennt
A <- Weil "B" seinen Vorgänger "A" kennt
B <- Weil "B" seinen Vorgänger "A" kennt
C <- Weil "B" seinen Nachfolger "C" kennt
Gut, bitte wirf zunächst Deinen Konstruktor weg. Und zwar vollkommen unabhängig davon, was Du eigentlich programmieren möchtest.
Dein Konstruktor kann nicht funktionieren, weil Du kein gültiges Element sinnvoll erzeugen kannst. Du erzeugst X als Vorgänger von Y und dann ein anderes X (sprich "nicht identisches"), was in der Liste auftritt. Das ist erstmal legitim, da Equals die Gleichheit gültig prüft. Aber hier wuseln jetzt schon zwei X in der Weltgeschickte herum, die gleich aussehen, aber eben nicht gleich sein müssen, also auch Dein Programm mal so oder mal so beeinflussen.
Verloren geht hier die Identität der Buchstaben. Wieviele Buchstaben gibt es denn? 26 vermute ich. Das werden nicht mehr und nicht weniger. Und es gibt auch keine Varianten von X. X ist immer X. Nur bei Dir nicht, bei Dir gibt es X und dann noch X und beide sind nicht identisch. Sie müssen auch nicht identisch sein, nur weil Equals das die Gleichheit bestätigt. Ein X mit Y als Nachfolger ist equals X mit A als Nachfolger - die sind gleich, aber sie sind eben nicht identisch. Je nachdem welches X Du fragst, funktioniert Deine Sortierung mal so oder mal so.

Und schon kommst Du in C# in Probleme, da Du die Identität der Buchstaben nur umständlich gewährleisten kannst. Schreibe eine Methode inject, womit Du Vorgänger und Nachfolger in die Objekte injiziert. Oder zwei Methoden setPrecessor und setSuccessor

Code: Alles auswählen

Buchstabe A( "A" );
Buchstabe B( "B" );
Buchstabe C( "C" );
...
Buchstabe Z( "Z" );

A.inject( null, B );
B.inject( A, C );
...
Z.inject( Y, null );
Damit wahrst Du schonmal die Identität der Objekte. Wenn Du den Konstruktor für Buchstabe noch Privat setzt und eine Klasse drumrumbastelst, die die Buchstaben Objekte als Singletons verwaltet (Java und C# erleichtern das Programmieren massiv...höhö), kommen wir langsam in den Bereich, wo Du halbwegs dafür garantieren kannst, Deine Programmierung sinnvoll abzusichern. Wir verlassen aber deutlich den Bereich von "Anfängergeeignet".

Zurück zum Sortierproblem:
Eine Sortierung ist immer ein lineares Problem. Das heißt, Du hast einen Zahlenstrang und den kannst Du nach vorne wie auch nach hinten durchgehen. Wenn Du die Reihenfolge der Buchstaben nicht für alle Buchstaben festlegst, so hast Du zwei unabhängige Probleme, die Du hintereinander setzt. Das ist eben keine lineare Sortierung mehr. Du musst erst herausfinden, welcher Buchstabe zu welchem Vergleich gehört, bevor Du vergleichen kannst.
Shrax hat geschrieben: Zum Verständnis:
Das Progamm soll im Endzustand von der Console
neue Buchstaben bekommen. Diese Buchstaben können dazu
einen Vorgänger oder Nachfolger haben.
Wurden ein paar Buchstaben eingegeben "Sortiert" das Programm
anhand der eingegbenen Buchstaben die Liste.
Dadurch "lernt" das Programm quasi durch die Buchstaben und deren Verknüpfungen
wie die richtige Reihenfolge des Alphabets ist.
Wie soll ein Programm gleichzeitig sortieren, wenn es dabei die Regeln des Sortierens erst kennenlernen muss!?

Dein Problem ist nicht durch das Vergleichen zweier nebeneinander stehenden Elemente lösbar.

Wie sortierst Du AXB? X weiß, dass vor Y kommt, aber kommt es nach A und vor B? B weiß, dass A vor B kommt, A hat keinen Plan. Heißt das jetzt dass X vor A oder nach B kommt? Wie sortierst Du AXC? A und C haben keinen Plan, X auch nicht. B könnte was dazu beitragen, aber hier ist kein B.
Wie sortierst Du XBY. B weiß, das X nicht direkt vor B gehört und Y nicht direkt nach B. B weiß also nicht, ob es vor X oder nach Y rücken soll. Vielleicht steht es da auch richtig!? Was X und Y wissen, interessiert B eigentlich nicht. Es hilft auch nicht, denn ob B vor XY oder nach XY kommt, weiß es dadurch auch nicht und B ist der einzige, den der Sortieralgorithmus gerade fragt, also auch der einzige, der hier gerade eine Entscheidung treffen kann, ob er nach rechts oder nach links sortiert wird. Und die kann B so nicht treffen.

Du musst erstmal eine Vorsortierung machen: Über welchen Block kann ich etwas aussagen. Wenn B weiß, dass A der Vorgänger ist, dann muss B A mitteilen, dass B der Nachfolger von A ist. Und da kommen wir wieder mit der Identität ins Spiel. Du hast beliebig viele Instanzen eines Buchstabens und wenn Du irgendeinem A erklärst, dass B der Nachfolger ist, dann wird das nicht das identische A sein, was Du später fragen wirst, wer sein Nachfolger ist. Es muss aber das identische A sein, denn nur dieses eine A hat gelernt, wer sein Nachfolger ist.
Wenn jeder weiß, wer Vorgänger oder Nachfolger ist, dann kannst Du Gruppen bilden. Ein Buchstabe gehört zur Gruppa ABC oder zur Gruppe XY oder zur Gruppe 'Ich habe gar keinen Plan'. Und so kannst Du zuerstmal Deine Eingabe nach Gruppen sortieren. Anschließend hast Du einen Liste wie "CABYX", die Du anschließend auf Vorgänger und Nachfolger sortieren kannst. Und wenn Y keinen Plan hat, wer der Vorgänger ist und C keinen Plan hat, wer Nachfolger ist, dann bleiben die so stehen, weil die Gruppen ja keinen Plan haben, wie sie sortiert werden.

Das ist deutlich mehr Arbeit als nur einen Comparer zu schreiben.

Shrax hat geschrieben:Das Problem liegt soweit ich sehe daran, dass der Comparer nur "gleich", "größer" oder "kleiner" kennt.
Man müsste dem Comparer noch die Information geben, dass es Objekte gibt die nicht Sortierbar sind.
Objekte, die nicht sortierbar sind, kann man - Sürprise, Sürprise - nicht sortieren.
Wenn Du also doch sortieren willst, musst Du Dir übergeordnete Kriterien suchen, nach denen Du sortieren kannst.
Shrax hat geschrieben:Diese müssten dann einfach an den Anfang oder das Ende der Liste geschoben werden. (Ist faktisch egal ob vorne oder hinten, Hauptsache sie bleiben in der Liste. Denn wenn das Programm neue "informationen" bekommt, ist es evtl. möglich diese zu sortieren.
Ist nicht egal, denn dann könnten ja auch Konstellationen wie AXC rauskommen.
Shrax hat geschrieben:Wie sage ich das dem Comparer? Ich dachte ich gebe dann einfach "0" für "gleich" zurück, aber
das haut anscheinend nicht hin.
Doch, ich denke, das haut ganz gut hin.

Aber wie findet das...

Code: Alles auswählen

            if(b2.Equals(b1.nachfolger))
                result = 1;
            else if (b2.Equals(b1.vorgaenger))
                result = -1;
            else
                result = 0;
...heraus, dass A < C ist?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Shrax
Beiträge: 87
Registriert: Sa Dez 27, 2008 8:08 pm

Re: C# - Sortieren von ArrayList

Beitrag von Shrax » Mi Jun 03, 2015 5:31 pm

Hallo Xin,

vielen Dank für deine Antwort.

Bevor ich mich nun an die Arbeit mache deine Verbesserungsvorschläge umzusetzen habe ich noch eine Frage die denke ich nötig ist um ein Teil deiner Antwort zu verstehen.

Warum sollte ich in diesem Fall das Singleton-Pattern nutzen? Allgemein fehlt mir leider das Verständnis wann genau das Singleton-Pattern anzuwenden ist.
Wikipedia sagt hier
"
Das Singleton findet Verwendung, wenn

nur ein Objekt zu einer Klasse existieren darf und ein einfacher Zugriff auf dieses Objekt benötigt wird oder
das einzige Objekt durch Unterklassenbildung spezialisiert werden soll.

"
Quelle: http://de.wikipedia.org/wiki/Singleton_ ... smuster%29



In diesem Fall dürfen doch mehrere "Buchstaben" existieren? Sicherlich, X sollte es nur einmal geben, aber auch "A" ist schließlich ein Objekt der selben Klasse.
Oder habe ich deine Antwort "Wenn Du den Konstruktor für Buchstabe noch Privat setzt und eine Klasse drumrumbastelst," falsch verstanden?



Ein wirklich wunderschönes Beispiel, warum man Programmieren bitte nicht in Java oder C# lernen sollte, weil man sich ansonsten auf kurz oder lang, mächte auf die Kauleiste legt. :-)
Ertappt und sicherlich im Recht.

Ja Xin, da hast du recht. Und ich werde sicherlich nicht widersprechen da Diskusionen um dieses Thema wohl in der Programmierung schon sehr oft geführt wurden und zweitens weil ich dir zustimme.
Leider hat man nicht immer die Wahl welche Programmiersprache man als erstes lernen soll. Aber ich verstehe was du damit sagen möchtest.
Andererseits sind es genau diese Fehler die einen weiterbringen.

"Den größten Fehler, den man im Leben machen kann, ist, immer Angst zu haben, einen Fehler zu machen."
Dietrich Bonhoeffer
Heute wird übrigens niemand mehr nach Lines of Code bezahlt.
Dankeschön für den Verbesserungsvorschlag. Ich denke kürzere Schreibweisen kommen mit der Zeit in der man Programmieren lernt - und man lernt ja nie aus.


Die anderen Punkte deiner Antwort versuche ich nun umzusetzen. Klingt soweit logisch, insofern vielen dank dafür.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: C# - Sortieren von ArrayList

Beitrag von Xin » Fr Jun 05, 2015 12:18 pm

Shrax hat geschrieben:Warum sollte ich in diesem Fall das Singleton-Pattern nutzen? Allgemein fehlt mir leider das Verständnis wann genau das Singleton-Pattern anzuwenden ist.
War blöd von mir ausgedrückt.

Singleton gilt für eine Instanz einer Klasse, ich meinte wirklich eine Instanz pro Element. Ich kann mich jetzt mit BuchstabeA : public Buchstabe rausreden, so dass BuchstabeA::Instanz für alle BuchstabeA bis BuchstabeZ ein Singleton darstellt... aber das wäre tatsächlich ein wenig herausgeredet :-D

Also 26 Instanzen, aber eben nicht mehr - und nicht weniger.
Shrax hat geschrieben:
Ein wirklich wunderschönes Beispiel, warum man Programmieren bitte nicht in Java oder C# lernen sollte, weil man sich ansonsten auf kurz oder lang, mächte auf die Kauleiste legt. :-)
Ertappt und sicherlich im Recht.

Ja Xin, da hast du recht. Und ich werde sicherlich nicht widersprechen da Diskusionen um dieses Thema wohl in der Programmierung schon sehr oft geführt wurden und zweitens weil ich dir zustimme.
Leider hat man nicht immer die Wahl welche Programmiersprache man als erstes lernen soll. Aber ich verstehe was du damit sagen möchtest.
Andererseits sind es genau diese Fehler die einen weiterbringen.
Nopes, das sind die Fehler, die einen Anfänger überfordern. Das Ziel sollte sein, einen Anfänger auf ein Level zu bringen, dass er solche Fehler schon nicht mehr begeht. Den Unterschied zwischen "das Gleiche" und "das Identische" sollte ein Entwickler frühzeitig bekommen.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten