Sortierverfahren

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Einleitung

Auf dieser Wiki-Seite wollen wir lernen, welche Sotierverfahren es gibt, wie wir sie benutzen können und wie diese Sortierverfahren arbeiten.

Darüber hinaus wollen wir verstehen, wie groß die Komplexität dieser Sortierverfahren ist, wie sich die Komplexität berrechnet und wie wir die verschiedenen Sotierverfahren klassifizieren können.

Letztlich wollen wir den Zusammenhang von Sotieralgorithmen zum (Schul-)Alltag herstellen.

Was sind Sortieralgorithmen

Ein Sortieralgorithmus ist ein Algorithmus, der dazu dient, eine Menge von Elementen (zum Beispiel Arrays) zu sortieren. Diese Menge von Elementen können aber nur sortiert werden, falls die Menge dieser Elemente eine Ordnung hat. Beispiele hierzu sind die Zahlen, die durch ihre numerische Ordnung (zum Beispiel 3<4) geordnet werden können.

Ein anderes Beispiel sind die Buchstaben unseres Alphabetes. Diese können nach ihrer lexikographischen Ordnung sortiert werden.

Die Farbe von Spielkarten wiederum könnte nicht sortiert werden. Hier gibt es keine Ordnung zwischen den einzelnen Farben.

Somit können also unter anderem Personen nach ihrem Geburtsjahr oder auch Namen nach ihrem Anfangsbuchstaben sortiert werden.

Komplexität

Was bedeutet Komplexität ?

Die Qualität von Algorithmen lässt sich nicht allein dadurch beurteilen, ob sie das gewünschte Ergebnis liefern. Die Qualität eines Algorithmus bestimmt vor allem die Laufzeit. Man möchte natürlich, dass der Algorithmus in der kürzesten Zeit terminiert. Die Laufzeit ist also ein entscheidendes Qualitätsmerkmal eines Algorithmus. Die Laufzeit eines Algorithmus wird oftmals auch als Komplexität bezeichnet. Wie sich diese Komplexität berechnet und welche Komplexitätsklassen es gibt, wollen wir uns im folgenden Abschnitt genauer anschauen.

Das Landau-Symbol

Das Landau-Symbol wird in der Informatik verwendet, um das Verhalten von Funktionen zu beschreiben. Insbesondere werden sie verwendet, um Algorithmen zu analysieren. Sie geben einem ein Maß für die Anzahl der Schritte, die der Algorithmus benötigt. Hat man die Komplexität von Algorithmen berrechnet, kann man sie vergleichen und dadurch abschätzen, welcher Algorithmus schneller arbeitet. Ein schlechter Wert beispielsweise ist exponentielles Wachstum. Der bestmögliche Wert ist ein konstanter Zeitaufwand.

Üblicherweise werden wir ausschließlich das O-Symbol benutzen. Werden wir eine Funktion einer O-Notation zuordnen, so ist diese die obere Schranke der Funktion. Somit lässt sich der Aufwand der Funktion (oder des Algorithmus) nach oben abschätzen.

Die wichtigsten Schrankenfunktionen :

konstant O(1)
logarithmisch O(log(n))
polylogarithmisch O(\log^k n) für k >1
linear O(n)
n-log-n O(n(log (n)))
quadratisch O(n^2)
polynomial O(n^k) für k > 1
exponentiell O(d^n) für d > 1


Wenn Sie mehr über das Landau-Symbol erfahren wollen, können Sie hier Landau-SymboleWikipedia-logo.png nachschlagen !

Berechnung von Komplexitäten

Die Berechnung von Komplexitäten ist eine komplizierte Angelegenheit. Leider kann man die Komplexität auch nicht immer nach demselben Schema berechnen. Wir wollen uns hier mit einigen Methoden der Komplexitätsberechnung auseinandersetzen.

Der naive Weg sieht folgendermaßen aus :

Der Algorithmus wird Zeile für Zeile auseinandergenommen. Der Gesamtaufwand eines Algorithmus berechnet sich aus der Summe der einzelnen Aufwände der Berechnungen.

Hier ist anzumerken, dass der Aufwand von Vergleichen, logischen Operationen, aritmetischen Operationen und das Einlesen von Daten einen konstanten Zeitaufwand haben.

Nehmen wir als kleines Beispiel den Aufwand einer for-Schleife, in der eine logische Operation bei jedem Schleifendurchgang durchgeführt wird. Wir nehmen an, die Schleife wird n-mal durchlaufen und der konstante Aufwand der logischen Operation sei c. Daraus würde sich als Komplexität der for-Schleife ergeben : T(n)= n*c (Es wird 'n' mal der Aufwand 'c' betrieben.)

Nehmen wir ein zweites Beispiel. Nehmen wir eine for-Schleife innerhalb einer for-Schleife. Dieses Beispiel könnte die Ausgabe aller Koordinaten in einem Kordinatensystem im zweidimensionalen Raum sein.

for(int x=0;x<n;x++){
                     for(int y=0;y<n;y++){
                     cout<<"Die Kordinaten von x und y sind:"                     
                     cout<<x;
                     cout<<y;
                                         }
                   }


Die erste for-Schleife wird n-mal durchlaufen. In jedem Durchlauf der ersten for-Schleife wiederum wird die zweite for-Schleife auch n-mal durchlaufen.

Nun wissen wir, die innere Schleife hat eine Komplexität von n*c (Siehe Beispiel oben). Weil nun 'n'-mal die äußere Schleife durchlaufen wird, erhalten wir für die Gesamtkomplexität T(n)= n*(n*c) = cn^2

Nach dem Landau-Symbol wissen wir nun, dass die Komplexität bei O(n^2) liegt (c ist ein konstanter Aufwand).


Nun wissen wir, dass wir bei komplexeren Funktionen den Aufwand der einzelnen Operationen aufaddieren. Ebenso wissen wir, dass wir bei inneren Schleifen die Aufwände miteinander multiplizieren. Somit haben wir genug Wissen, um einfach Komplexitätsberechnungen durchzuführen.

Für komplexere Probleme, wie zum Beispiel rekursive Funktionen, kann das Master-Theorem (Master-TheoremWikipedia-logo.png) sehr hilfreich sein. In der bei uns anstehenden Komplexitätsberechnung werden wir dies aber nicht brauchen.


Letztlich wollen wir uns die Laufzeit von Algorithmen noch genauer anschauen. Die Komplexität in konkreten Fällen schwankt natürlich je nach Eingabe. Ist die Eingabemenge etwa schon sortiert, braucht der Algorithmus nur konstante Zeit. Im schlechtesten Fall muss der Algorithmus die maximale Anzahl an Schritten durchführen, um zu einem Ergebnis zu kommen. Man unterscheidet also zwischen dem besten Fall (best case) und dem schlechtesten Fall (worst case). Letztlich interessiert uns aber am meisten die durschnittliche Laufzeit (average case). Dies ist die Laufzeit, die am häufigsten auftritt, und somit ausschlaggebend für die Qualität eines Sortieralgorithmus ist. Hier wird die Laufzeit für zufällige Eingabemengen berrechnet.

Aufgabe zum Ordnen von Komplexitäten

Damit wir die nun errechneten Komplexitäten nutzen können, sollten wir uns Gedanken machen über die Ordnung der Komplexitätsklassen. Im folgenden Quiz sollt ihr einige Fragen zur Ordnung der Komplexitätsklassen beantworten !

1. Welche Komplexitäsklasse hat die höchste Komplexität ?

O(n^2)
O(n^3)
O(log(n))

2. Welche Komplexitäsklasse hat die kleinste Komplexität ?

O(n^3)
O(n!)
O(n^n)

3. Welche der folgenden Komplexitäsklassen ist am optimalsten für einen Algorithmus ?

O(n(log(n)))
O(log(n))
O(n)

Punkte: 0 / 0


Ordnen Sie folgende Komplexitätsklassen nach aufsteigender Komplexität : O(n), O(1), O(n!), O(log(n)), O(\sqrt{n}) .


O(1) < O(log(n)) < O(\sqrt{n}) < O(n) < O(n!).


Sotieralgorithmen

Vergleichbasierende Sortieralgorithmen

Vergleichbasierende Sortieralgorithmen zeichnen sich dadurch aus, dass sie paarweise die einzelnen Elemente vergleichen.

Bubblesort

Funktionsweise

Bei Bubblesort wird die eingegebene Menge (Zahlen, Buchstaben etc.) einmal komplett durchlaufen. Dabei werden immer die beiden benachbarten Felder miteinander verglichen. Sollte das linke Element größer sein als das rechte, werden die beiden Elemente getauscht. Dies wird nun immer wieder wiederholt, bis der Algorithmus am Ende des Feldes angekommen ist. Nun startet der Algorithmus erneut bei dem vordersten Feld und läuft durch die gesamte Eingabemenge. Das letzte Feld aus dem vorherigen Durchgang muss aber nicht mehr beachtet werden, da dies schon als größtes Element erkannt wurde, und somit richtigerweise ganz rechts steht. Dies wird nun solange wiederholt, bis die Eingabenmenge vollständig sortiert ist.

Algorithmus

Der Algorithmus in seiner einfachsten Form könnte zum Beispiel so aussehen :


 bubbleSort(Array A)
 for (n=A.size; n>1; n=n-1){        //For-Schleife zum mehrfachen Durchlaufen des Feldes.
   for (i=0; i<n-1; i=i+1){
     if (A[i] > A[i+1]){           // Vergleich der benachbarten Elemente. Falls falsche Ordnung, tausche die Elemente.            
       A.swap(i, i+1)
     }
   } 
 }


Hier wird als Eingabemenge ein Array benutzt, das innerhalb der Schleifen sortiert wird. Gegebenenfalls kann man natürlich noch eine geeignete Ausgabe an den Algorithmus anhängen.

Der Bubblesort-Algorithmus lässt sich durch mehrere kleine Eingriffte auch noch optimieren. So wird hier noch nicht berücksichtigt, dass man das letzte Element nach jedem Durchlauf außen vor lassen kann. Dies erspart natürlich unnötige Vergleiche.

Beispiel

Bubble-sort Beispiel

Hier sehen Sie ein kleines Beispiel, wie Bubblesort vorgeht. Es werden immer die beiden Zahlen mit den roten Kästchen verglichen und gegebenenfalls vertauscht.

Komplexität

Vorbemerkung
Es wird davon ausgegangen, dass der Vergleich zweier Elemente konstanten Zeitaufwand benötigt.
Best case
Im besten Falle bekommt Bubblesort eine geordnete Eingabemenge. Bubblesort durchläuft also nur einmal die Menge, erkennt, dass alles sortiert ist, und beendet den Algorithmus. Die Lauftzeit beträgt also O(n) (wobei n die Anzahl der Elemente der Eingabemenge), da keine Elemente vertauscht werden müssen.


Worst case
Im schlechtesten Fall müssen wir jeden Durchgang die maximale Anzahl an Elementen tauschen. Das wären im ersten Durchgang n-1, im zweiten Durchgang n-2 usw.

Daraus ergibt sich für die Anzahl der Vertauschungen :


\sum_{k=1}^n-1 =


\frac{(n-1)(n-2)}{2} =


frac{n^2-3n+2}{2}


Und damit ergibt sich für die Komplexität O(n^2)


Average case : Betrachtet man ersteinmal die Anzahl der Vergleiche pro Durchlauf :

Diese sind : (n-1)+(n-2)+...+1 = 1/2 n^2 - 1/2 n

Nimmt man nun an, dass bei der Hälfte der Vergleiche wirklich Vertauschungen nötig sind, so kommt auf 1/4 n^2 - 1/4n Vertauschungen.

Somit nimmt Bubblesort im average case ebenso eine Komplexität von O(n^2) an ( Da 1/4n^2 - 1/4n /in O(n^2) )

Andere Vergleichbasierende Sortieralgorithmen

Andere Beispiele für vergleichsbasierende Sortieralgorithmen sind :

Nicht-vergleichbasierende Sortieralgorithmen

Radixsort

Funktionsweise

Radixsort besteht aus den Phasen Partionierungsphase und Sammelphase. Diese beiden Phasen werden bei radixsort immer abwechselnd ausgeführt. In der Partionierungsphase werden die verschiedenen Eingabewerte nach aufsteigender Wertigkeit ihres Alphabethes in Fächer geordnet. Hier wird bei dem Zeichen mit der niedrigsten Wertigkeit des Wortes begonnen ( bei einer Zahl mit der hintersten, bei einem Wort mit dem hintersten Buchstaben).


In der Sammelphase werden alle Wörter aus ihren Fächern wieder eingesammelt. Zuerst die Wörter aus dem Fächer mit der niedrigsten Wertigkeit, dann die Wörter aus dem Fächer mit der zweitniedrigsten Wertigkeit und so weiter. Wichtig hierbei ist, dass die Wörter in unveränderter Reihenfolge aus ihrem Fächer geholt werden.


Diese beiden Phasen werden abwechselnd solange durchgeführt, bis die Partionierungsphase und Sammelphase das Zeichen mit der höchsten Wertigkeit erreicht und bearbeitet haben.

Algorithmus

Beispiel

Betrachten wir das normale Alphabeth und die Wörter, bestehend aus drei Buchstaben. Seien unsere Eingabemenge die Wörter : ABC, DBC, BAD, DAB, ACB

In der ersten Partionierungsphase würden wir, unserem Alphabeth üblich, nach dem Buchstaben mit der niedrigsten Wertigkeit auffächern. Dies ist der hinterste. Also würde sich aus der ersten Partionierungsphase ergeben :


A B C D
DAB ABC BAD
ACB DBC


Nun würde die erste Sammelphase zu diesem Zwischenergebniss kommen : DAB, ACB, ABC, DBC, BAD

Die zweite Partionierungsphase liefert ( nun nach dem mittleren Buchstaben gefächert):

A B C D
DAB ABC ACB
BAD DBC


Nach der zweiten Sammelphase folge : DAB, BAD, ABC, DBC, ACB


Die letze Partionierungsphase ergibt :

A B C D
ABC BAD DAB
ACB DBC


Und hieraus folgt nach der letzten Sammelphase das gewünschte Ergebnis : ABC, ACB, BAD, DAB, DBC

Komplexität

Die Laufzeit von radixsort lässt sich mit O(m*n) abschätzen.

m ist hierbei die Länge des Schlüssels und n die Anzahl Elemente die sortiert werden sollen. Da für primitive Datentypen ( ganze Zahlen, Kommazahlen) m konstan ist, liefert radixsort hier sogar lineare Laufzeit. Für andere Datentypen erhöht sich die Komplexität jedoch deutlich.

Andere nicht-vergleichbasierende Sortieralgorithmen

-Bucketsort ( http://de.wikipedia.org/wiki/Bucketsort )

-Countingsort ( http://de.wikipedia.org/wiki/Countingsort )

Stabile Sortierverfahren

Stabile Sortierverfahren verändern die Reihenfolge mit gleichem Sortierschlüssel nicht. So wird zum Beispiel bei einem Datensatz mit Fahrrädern, die nach

ihrem Anfangsbuchstaben sortiert sind, die Reihenfolge der Fahrräder nicht verändert wenn wir nun die Fahrräder zusätzlich nach dem Preis sortieren. Das Fahrrad "Evans" mit dem

Preis von 500€ wird also weiterhin vor dem Fahrrad "Froome" ( ebenfalls mit einem Preis von 500€) aufgeführt.

Instabile Sortierverfahren können mit einem kleinen Trick in stabile Verfahren überführt werden. Es kann eine zusätzliche Reihenfolgenummer eingeführt werden mit der die Position der

verschiedenen Daten abgeglichen werden kann.

Stabile und nicht stabile Sortierverfahren müssen aber nicht zwangsweise verschiedene Ergebnisse liefern.


Beispiele für stabile Sortierverfahren sind : Mergesort, Bucketsort,,


Nicht stabile Sortierverfahren : Quicksort, Selectionsort


Aufgabe zu Stabilen/nicht Stabilen Sortierverfahren

1. Ist Bubblesort ein stabiler Sortieralgorithmus ?

Nein
Ja
Manchmal

2. Was für eine Art Sortieralgorithmus ist radixsort ?

Ein stabiler Sortieralgorithmus
Kein Stabiler Sortieralgorithmus
Kann man nicht genau sagen

Punkte: 0 / 0


In place/Out of place

Es wird bei Sortieralgorithmen zwischen Algorithmen unterschieden die in place arbeiten, und denen die out of place arbeiten. Wenn ein Algorithmus in place arbeitet, bedeutet dies der Algorithmus braucht einen konstanten, von der Eingabemenge unabhängigen Speicher. Dies bedeutet konkret, die Eingabedaten unseres Sortieralgorithmus werden mit den Ausgabedaten überschrieben. Das von uns vorhin unter die Lupe genommene Bubbelsort zum Beispiel arbeitet in place.


Bei Algorithmen die out of place arbeiten, müssen Daten zwischenzeitlich ausgelagert werden. So könnten Daten in einen Array oder in einer Liste zwischengespeichert werden bis sie für die Ausgabe wieder benötigt werden. Ein Beispiel für out of place ist Radixsort. Dadurch wird ein Algorithmus, der out of place arbeitet, in der Regel mehr Speicherplatzt benötigen wie ein in place Algorithmus.

Nutzung von Sortieralgorithmen

Im Alltag

Nun fragt ihr euch bestimmt, wo findet man denn sowas wie Sortieralgorithmen bzw Sortierverfahren im Alltag? Die Antwort: Man findet sie ziemlich oft versteckt in vielen Programmen!

Seien es Datenbankprogramme in denen angesammelte Daten nach Namen, Datum etc. sortiert werden sollen. Sei es die Fussballsimulation Fifa, in denen man seine Spieler nach der Anzahl der geschossenen Tore sortieren kann. Oder sei es vielleicht beim Sortieren eines Kartenspiels. Selbst hier wenden wir instinktiv einen Sortieralgorithmus an. Dieser ist zwar nicht zwanngsweise optimal, aber trotzdem ein Sortierverfahren.

Somit findet man tatsächlich in vielen Programmen oder täglichen Anwendungen Sortierverfahren. Vielleicht seht ihr nach dieser Selbstlerneinheit im Alltag öfters hinter die Kulissen und erkennt die Sortierverfahren die dahinter stecken.

In der Schule

Auch in der Schule lassen sich Sortieralgorithmen vielfältig in den Informatikunterricht einbauen.

Da Excel zum Beispiel sowieso ein fester Bestandteil der Schulinformatik ist, besteht hier die Möglichkeit Excel auf Sortieralgorithmen zu untersuchen. Wie funktioniert die von Excel bereitgestellte Sortierfunktion? Lassen sich in Excel auch andere Sortieralgorithmen implementieren? Hier gibt es also mehrere Möglichkeiten, die Sortieralgorithmen auch außerhalb einer Programmierumgebung kennenzulernen!

Sortieralgorithmen lassen sich auch wunderbar als Schülerprojekte realisieren. Sei es nun das Implementieren in einer Programmierumgebung oder auch nur die Funktionsweisen verbalisieren ( Die Schüler nach Alter sortieren mit Bubblesort zum Beispiel ). Auch hier lassen sich viele Ansätze finden, um Schüler ( auch spielerisch ) erste Kontakte mit Sortieralgorithmen knüpfen zu lassen!

Besonders in einer Informatik AG könnte man über mehrere Wochen ein Projekt zu Sortierverfahren großartig aufziehen.

Also selbst ohne konkret den Code von Sortierverfahren anzulangen kann man schon viele Sortierverfahren kennenlernen und sich mit deren Funktionsweisen vertraut machen. Den Schülern kann dies besonders mit vielen Alltagsbeispielen ( Karten sortieren usw ) schmackhaft gemacht werden.

Alles verstanden?

Zum Abschluss wollen wir noch einen kleinen Test starten. Haben Sie wirklich alles verstanden?

Es kann mehrere richtige Antworten geben!

Ist Bubblesort ein stabiler Sortieralgorithmus? (Ja) (!Nein)

Kann man jeden Sortieralgorithmus zu einen stabilen Sortieralgorithmus machen? (!Nein) (Ja) (!Nicht jeden, nur manche)

Welchen Aufwand hat das Vertauschen zweier Elemente? (!Quadratischen Aufwand) (!Linearen Auwand) (Konstanten Aufwand)

Welchen Nachteil hat ein Out-of-place Sortierverfahren? (!Höhere Komplexität) (Größerer Speicherplatz) (!Keinen)

Radixsort ist ein... ? (!In-place Algorithmus) (Stabiler Algorithmus) (Algorithmus der zusätzlichen Speicherplatz brauch)

Welche dieser Algorithmen sind stabil? (Bubblesort) (Mergesort) (!Quicksort)

Brauch ein Algorithmus für jede Eingabemenge dieselbe Zeit für die Berrechung des Ergebnisses? (!Ja)(Nein)