Sortierverfahren

Sortieren

Einführung

Einführung Sicht des Computers Bubble Sort Insertion Sort Selection Sort Animation Bewertung von Verfahren

Das Ziel von Sortierverfahren besteht darin, die Reihenfolge von Elementen einer Menge so zu verändern, dass sie bezüglich eines Merkmals geordnet sind.

Gerade in der heutigen Zeit, in der das Sammeln von Daten nie geahnte Dimensionen angenommen hat, ist das Sortieren der Daten nach bestimmten Kriterien eine wichtige Aufgabe.

Die Suche in elektronischen Telefonbüchern wäre fast aussichtslos, wenn man nicht vorher nach Orten und Namen sortieren könnte.
Elektronische Wörterbücher lassen sich sinnvoll erst durchforsten, wenn die Wörter alphabetisch geordnet wurden.
In großen Krankenhäusern sollten Behandlungsreihenfolgen hauptsächlich durch die Dringlichkeit der Maßnahmen bestimmt sein.

Probleme oder warum werden so viele Sortierverfahren entwickelt

Geschwindigkeit	Beim Sortieren hat man es mit zwei Grundtätigkeiten zu tun. Beim Vergleichen überprüft man, ob die Werte bereits in der richtigen Reihenfolge vorliegen. Ist dies nicht der Fall, so wird die Reihenfolge durch Tauschen korrigiert. Jede Vergleichs- und Tauschoperation benötigt Zeit zur Ausführung. Je weniger dieser Operationen notwendig sind, desto schneller dürfte der Sortiervorgang ablaufen.
Anzahl der zu sortierenden Elemente	Welcher Zusammenhang besteht zwischen der Anzahl der Elemente und der Anzahl der notwendigen Vergleichs- und Tauschoperationen? Bei kleineren Datenmengen wird dieses Problem durch die Geschwindigkeit heutiger Rechner kaschiert. Bei größeren Beständen ist der Unterschied zwischen einem linearen und quadratischen Zusammenhang etwa so, als ob ich zwischen 1.000.000 oder 1.000.000.000.000 Operationen entscheiden müsste.
Stabilität	Was passiert mit einer sortierten Menge, wenn ich diese nachträglich nach einem neuen Kriterium sortiere? Bleibt die Vorsortierung wenigstens teilweise erhalten? In einem Telefonbuch könnte ich z.B. die Namen der Personen eines Ortes alphabetisch sortiert anzeigen lassen. Wenn ich jetzt die Liste nach Straßen sortiere, werden mir dann die Namen der Personen einer Straße noch in alphabetischer Reihe angezeigt?
Grad der Vorsortierung	Sicher wird man verschiedene Sortierverfahren verwenden, wenn man: eine völlig unsortierte Menge hat oder eine sortierte Menge hat, zu der noch ein Element dazu kommt, welches eingeordnet werden muss oder eine anders herum sortierte Liste von Elementen hat oder bereits eine sortierte Menge vor sich hat. Wie effizient sind die Verfahren bei unterschiedlichen Voraussetzungen?
Datenstruktur	Wie aufwendig sind Vergleichs- und Tauschoperationen mit den gegebenen Datentypen? Sind die Daten irgendwo zentral abgelegt oder liegen sie verteilt im Netzwerk?
Implementierung	Je komplizierter die Ausgangssituation ist, je mehr Sonderfälle zu berücksichtigen sind, desto komplexer werden die Programme, demzu folge steigt auch die Fehleranfälligkeit. Das Erkennen, ob einer der Sonderfälle eingetreten ist, benötigt Rechenzeit, die ein Verfahren ausbremsen kann.
Aktualität	Wie reagiert ein Sortierverfahren, wenn sich während der Ausführung der Datenbestand ändert? Wenn beispielsweise in einem Kaufhaus eine Liste der dringend nachzubestellenden Dinge erstellt werden soll, obwohl der Verkauf noch läuft.
Systemanforderungen	Welche Anforderungen stellt das Sortierverfahren an die Rechentechnik? Wie viel zusätzlicher Speicher wird benötigt? Reicht mein Computer, wenn ein Verfahren zwar sehr schnell ist, dazu aber den kompletten Datenbestand zwei oder mehrfach kopieren muss? Dies gilt vor allem für rekursive Verfahren.

Wie tauscht man zwei Elemente?

 void tausche(int a, int b) {
      a = b;
      b = a;
 }

Diese Methode funktioniert nicht.
Hat a beispielsweise den Wert 5 und b den Wert 3, so passiert folgendes:
In der ersten Zeile wird a der Wert von b zugewiesen also 3, a ist jetzt 3.
In der zweiten Zeile erhält b den Wert von a, welcher inzwischen 3 ist. Also haben beide Variablen am Ende der Prozedur den Wert 3. Es erfolgte kein Tausch.

Anweisung	a = 5;	b = 3;	a = b;	b = a;
Werte	a = 5 b =	a = 5 b = 3	a = 3 b = 3	a = 3 b = 3

 void tausche(int a, int b) {
     int c;

     c = a;
     a = b;
     b = c;
 }

Das Problem der vorigen Methode lässt sich lösen, indem man sich vor der Zuweisung den Wert einer Variablen in einer Hilfsvariablen sichert.
Hier wurde der Wert von a in c gesichert, c ist jetzt also 5. Anschließend erhält a den Wert von b, a ist jetzt 3. Nun erhält b den in c gesicherten Wert von a, b ist jetzt 5. Der Tausch ist erfolgt.

Anweisung	a = 5;	b = 3;	c = a;	a = b;	b = c;
Werte	a = 5 b = c =	a = 5 b = 3 c =	a = 5 b = 3 c = 5	a = 3 b = 3 c = 5	a = 3 b = 5 c = 5

zurück