Anleitungen:Listen von beliebigen Elementen sortieren: Unterschied zwischen den Versionen

Version vom 11. Juli 2012, 10:33 Uhr

Es ist leicht möglich, dass der Befehl Sortiere eine Liste von Objekten in GeoGebra nicht in der Art und Weise sortiert, wie Sie es gerne hätten. (Wenn Sie die Sortierung umkehren wollen, verwenden Sie den Befehl Sortiere in Kombination mit dem Befehl Umkehren.)

Für den Fall, dass der Befehl Sortiere die Elemente der Liste nicht ordnen kann oder Sie ein anderes Ordnungskriterium benötigen, kann Ihnen diese Anleitung helfen. Zum besseren Verständnis des Algorithmus finden Sie im Anschluss daran Erklärungen und Beispiele.

Algorithmus

Sei Liste jene Liste, die Sie sortieren wollen.
Liste_h = Sortiere[Folge[(*Zahl/Befehl bezüglich Element[Liste, i]*, i), i, 1, Länge[Liste]]]
Diese Hilfsliste wird in der anschließenden Erklärung mit c bezeichnet, der fett markierte Teil mit f.
Liste_s = Folge[Element[Liste, y(Element[Liste_h, i])], i, 1, Länge[Liste]]
Dies erstellt die gewünschte, sortierte Liste.

Erklärung

Um diesen Algorithmus etwas verständlicher zu machen, versuchen wir eine mathematische Formulierung:

Gegeben seien die Liste (a_1, a_2, \ldots, a_n) \subset X und die Abbildung f: X \to \mathbb R. Gesucht ist jene Permutation \sigma \in S_n, für die gilt: f(a_{\sigma(k)}) \leq f(a_{\sigma(l)}) \; \forall (k,l) \in \mathbb N^2: 1 \leq k \leq l \leq nDiese Permutation können Sie sich als Umnummerierung vorstellen, sodass (a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)}) die gewünschte, sortierte Liste ist.

Zu Beginn muss also die passende Abbildung f gefunden werden, beispielsweise:

Beispiel: Wenn Sie eine Liste von Punkten nach aufsteigendem Abstand vom Koordinatenursprung sortieren wollen, so ist X := \mathbb R^2 und f((x,y)) := \sqrt{x^2 + y^2}. In GeoGebra entspricht f für einen Punkt A dem Befehl Länge[A], also lautet der fett markierte Teil im Algorithmus: Länge[Element[Liste,i]].

Beispiel: Wenn Sie eine Liste von Kreisen nach aufsteigendem Radius sortieren wollen, so lautet der fett markierte Teil im Algorithmus: Radius[Element[Liste,i]].

Beispiel: Eine vollständige Ausführung, wie eine Liste komplexer Zahlen nach ihren Argumenten sortiert werden kann, finden Sie auf GeoGebra: http://www.geogebra.org/material/show/id/7518

Der Trick, dieses Problem in GeoGebra zu lösen, besteht darin, unter Verwendung von bereits bestehenden Befehlen eine Liste von Punkten zu sortieren. Dabei müssen Sie sich die Punkte als Zahlenpaare vorstellen. GeoGebra sortiert Punkte nach der x-Koordinate, weshalb wir eine Liste von Punkten \tilde c = (\tilde c_1, \ldots, \tilde c_n) mit \tilde c_k := (f(a_k), k) erzeugen und diese sortieren. Sei c = (c_1, \ldots, c_n) nun die sortierte Liste. Diese ermöglicht, \sigma zu konstruieren, da y(c_{\sigma(k)}) = k. Unter Verwendung dieses \sigma lässt sich dann die gewünschte, sortierte Version der ursprünglichen Liste erzeugen.

Wie werden Namen sortiert?

Angenommen, Sie haben die fünf Punkte mit den Namen A, B, C, D und E erzeugt und wollen diese nach einem gewissen Kriterium sortieren. Durch Erstellen der Liste = {A,B,C,D,E} und Anwenden des obigen Algorithmus erfolgt die gewünschte Sortierung, allerdings gibt GeoGebra nur die sortierte Liste mit den Koordinaten der Punkte aus, nicht aber die sortierte Liste mit den Namen der Punkte. Um die dazugehörige Liste der Namen zu erhalten, muss der Algorithmus etwas erweitert werden:

Sei Liste_n jene Liste mit den Namen der Objekte, die Sie sortieren wollen.
Zum Beispiel: Liste_n = {"A", "B","C","D","E"}. Vergessen Sie die Anführungsstriche nicht! - Sie wollen ja die Namen der Objekte, nicht die Objekte selber!
Erstellen Sie die Liste Liste=Folge[Objekt[Element[Liste_n, k]], k, 1, Länge[Liste_n]].
Das ist die Liste der zu den Namen gehörenden Objekte, die Sie sortieren wollen.
Liste_h = Sortiere[Folge[(*Zahl/Befehl bezüglich Element[Liste, i]*, i), i, 1, Länge[Liste]]]
(Schritt 2 des ursprünglichen Algorithmus)
Liste_{ns} = Folge[Element[Liste_n, y(Element[Liste_h, i])], i, 1, Länge[Liste]]
Dies ist die sortierte Liste mit den Namen der Objekte, beispielsweise {"B", "A", "E", "F", "D"}. Um auch die sortierte Liste mit den Werten zu erhalten, verwenden Sie Liste_s, wie im ursprünglichen Algorithmus beschrieben.

Beispiel: Das dritte Beispiel von oben mit Verwendung des erweiterten Algorithmus finden Sie ebenfalls in GeoGebra: http://www.geogebra.org/material/show/id/7775

es:Tutorial:Orden de Listas Avanzado fr:Tutoriel:Tri pointu pour une liste en:Tutorial:Advanced List Sorting

@@ Zeile 1: / Zeile 1: @@
+Es ist leicht möglich, dass der Befehl [[Sortiere_(Befehl)|Sortiere]] eine Liste von Objekten in GeoGebra nicht in der Art und Weise sortiert, wie Sie es gerne hätten. (Wenn Sie die Sortierung umkehren wollen, verwenden Sie den Befehl [[Sortiere_(Befehl)|Sortiere]] in Kombination mit dem Befehl [[Umkehren_(Befehl)|Umkehren]].)
+Für den Fall, dass der Befehl <code>Sortiere</code> die Elemente der Liste nicht ordnen kann oder Sie ein anderes Ordnungskriterium benötigen, kann Ihnen diese Anleitung helfen. Zum besseren Verständnis des Algorithmus finden Sie im Anschluss daran Erklärungen und Beispiele.
+== Algorithmus ==
+# Sei <code>Liste</code> jene Liste, die Sie sortieren wollen.
+# <code>Liste_h = Sortiere[Folge[('''*Zahl/Befehl bezüglich Element[Liste, i]*''', i), i, 1, Länge[Liste]]]</code> <br /> Diese ''Hilfsliste'' wird in der anschließenden Erklärung mit <math>c</math> bezeichnet, der fett markierte Teil mit <math>f</math>.
+# <code>Liste_s = Folge[Element[Liste, y(Element[Liste_h, i])], i, 1, Länge[Liste]]</code> <br /> Dies erstellt die gewünschte, sortierte Liste.
+== Erklärung ==
+Um diesen Algorithmus etwas verständlicher zu machen, versuchen wir eine mathematische Formulierung:
+:Gegeben seien die Liste <math>(a_1, a_2, \ldots, a_n) \subset X</math> und die Abbildung <math>f: X \to \mathbb R</math>. Gesucht ist jene Permutation <math>\sigma \in S_n</math>, für die gilt: <math>f(a_{\sigma(k)}) \leq f(a_{\sigma(l)}) \; \forall (k,l) \in \mathbb N^2: 1 \leq k \leq l \leq n</math>Diese Permutation können Sie sich als Umnummerierung vorstellen, sodass  <math>(a_{\sigma(1)}, a_{\sigma(2)}, \ldots, a_{\sigma(n)})</math> die gewünschte, sortierte Liste ist.
+Zu Beginn muss also die passende Abbildung <math>f</math> gefunden werden, beispielsweise:
+{{example|1=
+Wenn Sie eine Liste von Punkten nach aufsteigendem Abstand vom Koordinatenursprung sortieren wollen, so ist <math>X := \mathbb R^2</math> und <math>f((x,y)) := \sqrt{x^2 + y^2}</math>. In GeoGebra entspricht <math>f</math> für einen Punkt <code>A</code> dem Befehl <code>Länge[A]</code>, also lautet der fett markierte Teil im Algorithmus: <code>Länge[Element[Liste,i]]</code>.}}
+{{example|1=Wenn Sie eine Liste von Kreisen nach aufsteigendem Radius sortieren wollen, so lautet der fett markierte Teil im Algorithmus: <code>Radius[Element[Liste,i]]</code>.}}
+{{example|1=Eine vollständige Ausführung, wie eine Liste komplexer Zahlen nach ihren Argumenten sortiert werden kann, finden Sie auf GeoGebra: http://www.geogebra.org/material/show/id/7518
+}}
+Der Trick, dieses Problem in GeoGebra zu lösen, besteht darin, unter Verwendung von bereits bestehenden Befehlen eine Liste von Punkten zu sortieren. Dabei müssen Sie sich die Punkte als Zahlenpaare vorstellen. GeoGebra sortiert Punkte nach der ''x''-Koordinate, weshalb wir eine Liste von Punkten <math>\tilde c = (\tilde c_1, \ldots, \tilde c_n)</math> mit <math>\tilde c_k := (f(a_k), k)</math> erzeugen und diese sortieren.
+Sei <math>c = (c_1, \ldots, c_n)</math> nun die sortierte Liste. Diese ermöglicht, <math>\sigma</math> zu konstruieren, da <math>y(c_{\sigma(k)}) = k</math>. Unter Verwendung dieses <math>\sigma</math> lässt sich dann die gewünschte, sortierte Version der ursprünglichen Liste erzeugen.
+== Wie werden Namen sortiert? ==
+Angenommen, Sie haben die fünf Punkte mit den Namen <code>A</code>, <code>B</code>, <code>C</code>, <code>D</code> und <code>E</code> erzeugt und wollen diese nach einem gewissen Kriterium sortieren. Durch Erstellen der <code>Liste = {A,B,C,D,E}</code> und Anwenden des obigen Algorithmus erfolgt die gewünschte Sortierung, allerdings gibt GeoGebra nur die sortierte Liste mit den Koordinaten der Punkte aus, nicht aber die sortierte Liste mit den Namen der Punkte. Um die dazugehörige Liste der Namen zu erhalten, muss der Algorithmus etwas erweitert werden:
+#  Sei <code>Liste_n</code> jene Liste mit den ''Namen der Objekte'', die Sie sortieren wollen.<br />Zum Beispiel: <code>Liste_n = {"A", "B","C","D","E"}</code>. <small>Vergessen Sie die Anführungsstriche nicht! - Sie wollen ja die Namen der Objekte, nicht die Objekte selber!</small>
+# Erstellen Sie die Liste <code>Liste=Folge[Objekt[Element[Liste_n, k]], k, 1, Länge[Liste_n]]</code>.<br />Das ist die Liste der zu den Namen gehörenden Objekte, die Sie sortieren wollen.
+# <code>Liste_h = Sortiere[Folge[('''*Zahl/Befehl bezüglich Element[Liste, i]*''', i), i, 1, Länge[Liste]]]</code> <br /> (Schritt 2 des ursprünglichen Algorithmus)
+# <code>Liste_{ns} = Folge[Element[Liste_n, y(Element[Liste_h, i])], i, 1, Länge[Liste]]</code> <br />Dies ist die sortierte Liste mit den Namen der Objekte, beispielsweise <code>{"B", "A", "E", "F", "D"}</code>. Um auch die sortierte Liste mit den Werten zu erhalten, verwenden Sie <code>Liste_s</code>, wie im ursprünglichen Algorithmus beschrieben.
+{{example|1=
+Das dritte Beispiel von oben mit Verwendung des erweiterten Algorithmus finden Sie ebenfalls in GeoGebra: http://www.geogebra.org/material/show/id/7775
+}}
 [[Category:Advanced Tutorials]]
 [[es:Tutorial:Orden de Listas Avanzado]]
 [[fr:Tutoriel:Tri pointu pour une liste]]
 [[en:Tutorial:Advanced List Sorting]]