Sortieralgorithmen/ Selectionsort

Aus Wikibooks
Zur Navigation springen Zur Suche springen


Selectionsort ist ein einfaches Sortierverfahren. Ein anderer Name für Selectionsort ist Exchangesort (Austauschsortierung). (12) Selection kommt aus dem Englischen und bedeutet Auswahl.

Dieses Sortierverfahren arbeitet in-place.

In diesem Verfahren wird die erste Zahl der Zahlenreihe genommen. Dieser Zahl wird dann der Wert "kleinste Zahl" zugewiesen. Nun wird verglichen, ob die zweite Zahl größer, oder kleiner, als die erste Zahl ist. Ist diese kleiner, bekommt sie den Wert "kleinste Zahl" zugewiesen. Diese Zahl wird in ein Feld gelegt, in dem die sortierten Zahlen gesammelt werden. In ein sogenanntes Array. (13) Sollte diese Zahl jedoch größer sein, als die erste, bleibt alles so wie es ist.

Im nächsten Schritt wird die nun "kleinste Zahl" mit der dritten Zahl verglichen. Ist diese größer, bleibt alles wie vorher, ist sie jedoch kleiner, bekommt sie nun den Wert "kleinste Zahl" zugewiesen. Nun geht diese Methode solange weiter, bis der PC bei der letzten Zahl angelangt ist. Jetzt wird die kleinste Zahl genommen und mit der Zahl an erster Stelle getauscht.

Im nächsten Schritt fängt alles von neuem an, diesmal jedoch mit der zweiten Zahl. Ist dieser wieder bei der letzten Zahl angelangt, wird hier die "kleinste Zahl" logischerweise mit der 2 Zahl vertauscht. Dieses Sortierverfahren wird nun solange durchlaufen, bis alle Zahlen sortiert sind.

Auch hier werde ich das Sortierverfahren jetzt an einem Beispiel bildhaft darstellen. Andreas ist ein leidenschaftlicher Fifa Spieler. Seit 2010 kauft und sammelt er jedes Fifa Spiel. Da sie immer unsortiert herumliegen, will er sie nach Erscheinungsjahr sortieren.

Also stapelt er alle, nimmt sich dann das auf dem Stapel ganz oben liegende Spiel von 2012 und sagt, das ist das älteste Spiel, bis ich ein älteres gefunden habe. Dann nimmt er das zweite Spiel, welches von 2014 ist. Da es jünger, als das erste Spiel ist, legt er es auf einen neuen Stapel.

Jetzt nimmt er das nächste Spiel, welches 2010 erschienen ist und vergleicht es mit dem ersten. Da das Spiel, welches er vom Stapel genommen hat von 2010 ist und das, welches er in der Hand hält von 2012 stammt, legt er das 2012 entwickelte Spiel auf den zweiten Stapel und bestimmt das andere als das älteste.

Im nächsten Schritt vergleicht Andreas das Spiel von 2010 mit allen anderen Spielen. Doch kein Spiel ist älter, als dieses, also legt er es extra hin und sagt, dass dieses Spiel sortiert ist.

Jetzt nimmt er alle anderen Spiele und fängt wieder von vorne an. Als erstes, nimmt er sich dann das auf dem Stapel ganz oben liegende Spiel aus dem Jahr 2013 und sagt wieder, das dies das älteste sei, bis er ein älteres finden würde. Jetzt vergleicht er das mit dem zweiten Spiel, welches von 2011 ist, also sagt er, dass das Spiel von 2011 nun das älteste sei und legt das von 2013 auf einen extra - Stapel. Andreas vergleicht nun das Spiel von 2011 mit den anderen Spielen, da es das älteste ist kommt auch dieses auf den Stapel der sortierten Spiele.

Als nächstes nimmt sich Andreas wieder das erste Spiel vom unsortierten Stapel und vergleicht es mit den anderen und so weiter. Am Ende hat Andreas alle seine Spiele fertig sortiert.