Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


8. Elementare Sortierverfahren



Kenngrößen der Leistungsfähigkeit elementarer Sortiermethoden

Die Abbildungen 8.3, 8.4 und 8.5 dienen zur direkten Veranschaulichung der Merkmale der Arbeitsweise von Selection Sort, Insertion Sort und Bubble Sort. Diese Abbildungen zeigen den Inhalt des Feldes a für jeden der Algorithmen, nachdem die äußere Schleife N/4, N/2 und 3N/4 mal durchlaufen worden ist (beginnend mit einer zufälligen Permutation der ganzen Zahlen 1 bis N als Eingabe). In den Diagrammen wurde für a[i]=j ein Quadrat an die Stelle (i,j) gesetzt. Ein ungeordnetes Feld entspricht damit einer zufälligen Anordnung von Quadraten; in einem sortierten Feld erscheint jedes Quadrat oberhalb des links von ihm befindlichen Quadrates. Zur Klarheit der Abbildungen zeigen wir Permutationen (zufällige Anordnungen der ganzen Zahlen 1 bis N), für die nach dem Sortieren die Quadrate alle längs der Hauptdiagonale angeordnet sind. Die Bilder zeigen, wie sich die verschiedenen Methoden auf dieses Ziel hin bewegen.

Abbildung 8.3 zeigt, wie sich Selection Sort von links nach rechts bewegt, wobei es Elemente in ihre endgültige Position bringt, ohne »zurückzublicken«. Was aus diesem Bild nicht ersichtlich ist, ist die Tatsache, daß bei Selection Sort die meiste Zeit dafür aufgewandt wird, das minimale Element in dem »unsortierten« Teil des Feldes zu suchen.

Abbildung 8.3
Abbildung 8.3 Sortieren einer zufälligen Permutation durch Selection Sort.

Abbildung 8.4 zeigt, wie sich Insertion Sort gleichfalls von links nach rechts bewegt, wobei neu vorgefundene Elemente an der entsprechenden Stelle eingefügt werden, ohne daß weiter nach vorn geschaut wird. Der linke Teil des Feldes verändert sich ständig.

Abbildung 8.4
Abbildung 8.4 Sortieren einer zufälligen Permutation durch Insertion Sort.

Abbildung 8.5 zeigt die Ähnlichkeit zwischen Selection Sort und Bubble Sort. Bei Bubble Sort wird auf jeder Stufe das größte verbliebene Element ausgewählt, doch es wird einige Mühe dafür »vergeudet«, im »unsortierten« Teil des Feldes eine gewisse Ordnung herzustellen.

Abbildung 8.5
Abbildung 8.5 Sortieren einer zufälligen Permutation durch Bubble Sort.

Alle Verfahren sind sowohl im ungünstigsten als auch im durchschnittlichen Fall quadratisch und erfordern keinen zusätzlichen Speicherplatz. Daher sind Vergleiche zwischen ihnen von der Länge der inneren Schleifen oder von speziellen Merkmalen der Eingabedaten abhängig.

Eigenschaft 8.1 Selection Sort benötigt ungefähr N2/2 Vergleiche und N Austauschoperationen.

Diese Eigenschaft läßt sich leicht einsehen, wenn man Abbildung 8.1 betrachtet, bei der es sich um eine Tabelle von der Größe N x N handelt, in der ein Buchstabe jeweils einem Vergleich entspricht. Doch dies betrifft etwa die Hälfte der Elemente, und zwar diejenigen oberhalb der Diagonalen. Die N - 1 Elemente auf der Diagonalen (mit Ausnahme des letzten) entsprechen jeweils einem Austausch. Genauer: Für jedes i von 1 bis N - 1 erfolgen ein Austausch und N - i Vergleiche, wodurch sich eine Gesamtzahl von N - 1 Austauschoperationen und (N - 1) + (N - 2) +...+ 2 + 1 = N (N - 1) / 2 Vergleichen ergibt. Diese Beobachtungen gelten unabhängig davon, welche Eingabedaten vorliegen; der einzige Teil von Selection Sort, der von den Eingabedaten abhängt, ist die Anzahl, wie oft min einen neuen Wert zugewiesen bekommt. Im ungünstigsten Fall könnte dies ebenfalls eine quadratische Funktion von N sein, im durchschnittlichen Fall erweist es sich jedoch, daß diese Größe nur O (N log N) ist, so daß zu erwarten ist, daß die Laufzeit von Selection Sort relativ unempfindlich gegenüber Änderungen der Eingabedaten ist. w.z.b.w.

Eigenschaft 8.2 Insertion Sort benötigt im Durchschnitt ungefähr N2/4 Vergleiche und N2/8 Austauschoperationen, im ungünstigsten Fall doppelt so viele.

Wie aus der obigen Implementation ersichtlich ist, ist die Anzahl der Vergleiche und der »halben Austausche« (Bewegungen) die gleiche. Diese Größe läßt sich leicht anhand Abbildung 8.2 veranschaulichen, der N x N - Tabelle, die die Arbeitsweise des Algorithmus im einzelnen zeigt. In diesem Falle sind die Elemente unterhalb der Diagonalen zu zählen, im ungünstigsten Fall alle. Für zufällige Eingabedaten ist zu erwarten, daß sich jedes Element im Durchschnitt etwa den halben Weg zurück bewegt, so daß die Hälfte der Elemente unterhalb der Diagonalen zu zählen wäre. (Es ist nicht schwierig, diese Überlegungen exakter zu formulieren.) w.z.b.w.

Eigenschaft 8.3 Bubble Sort benötigt im Durchschnitt und im ungünstigsten Fall ungefähr N2/2 Vergleiche und N2/2 Austauschoperationen.

Im ungünstigsten Fall (Datei in umgekehrter Reihenfolge) ist es klar, daß der i-te Durchlauf von Bubble Sort N - i Vergleiche und Austauschoperationen erfordert, so daß der Beweis wie für Selection Sort geführt werden kann. Jedoch ist die Laufzeit bei Bubble Sort von den Eingabedaten abhängig. Wir sehen zum Beispiel, daß nur ein Durchlauf benötigt wird, wenn die Datei bereits geordnet ist (Insertion Sort ist in diesem Falle auch schnell). Es zeigt sich, daß - wie oben erwähnt - die Leistungsfähigkeit im durchschnittlichen Fall nicht wesentlich besser ist als im ungünstigsten Fall; diese Analyse ist jedoch wesentlich komplizierter. w.z.b.w.

Eigenschaft 8.4 Insertion Sort ist für »fast sortierte« Dateien linear.

Obwohl der Begriff einer »fast sortierten« Datei notwendigerweise recht ungenau ist, läßt sich Insertion Sort gut auf gewisse nichtzufällige Dateien anwenden, die in der Praxis oft auftreten. Gewöhnlich werden für solche Anwendungen unnötigerweise Mehrzweck-Sortierverfahren benutzt; in Wirklichkeit kann Insertion Sort aus der in der Datei vorhandenen Ordnung Nutzen ziehen.

Betrachten wir zum Beispiel den Ablauf von Insertion Sort für eine Datei, die bereits sortiert ist. Jedes Element wird sofort als an seinem richtigen Platz in der Datei befindlich erkannt, und die Gesamtlaufzeit ist linear. Das gleiche gilt für Bubble Sort. Selection Sort jedoch ist nach wie vor quadratisch. Sogar dann, wenn eine Datei nicht vollständig sortiert ist, kann Insertion Sort recht zweckmäßig sein, da seine Laufzeit stark von der in der Datei vorhandenen Ordnung abhängt. Die Laufzeit ist von der Anzahl der Inversionen abhängig: Für jedes Element sind dazu die links von ihm befindlichen Elemente zu zählen, die größer sind. Dies ist der Abstand, um den die Elemente bewegt werden müssen, wenn sie bei Insertion Sort in die Datei eingefügt werden. Eine Datei, in der eine gewisse Ordnung vorhanden ist, weist weniger Inversionen auf als eine zufällig zusammengestellte Datei.

Nehmen wir an, zu einer sortierten Datei sollen einige Elemente hinzugefügt werden, so daß eine größere sortierte Datei erzeugt wird. Ein Weg zur Realisierung besteht darin, die neuen Elemente an das Ende der Datei anzuhängen und dann einen Sortieralgorithmus aufzurufen. Es ist klar, daß die Anzahl der Inversionen in einer solchen Datei gering ist: Eine Datei, in der sich nur eine konstante Zahl von Elementen nicht an ihrem Platz befindet, weist nur eine lineare Anzahl von Inversionen auf. Ein anderes Beispiel ist eine Datei, in der jedes Element sich nur in einem gewissen konstanten Abstand von seiner endgültigen Position befindet. Dateien dieser Art können in den Anfangsstadien einiger weiterentwickelter Sortierverfahren erzeugt werden; zu einem gewissen Zeitpunkt lohnt es sich dann, zu Insertion Sort überzuwechseln.

Für derartige Dateien ist Insertion Sort in Bezug auf die Leistung sogar den komplizierten Verfahren überlegen, die in den nachfolgenden Kapiteln beschrieben werden. w.z.b.w.

Um den Vergleich der Methoden weiterzuführen, ist es erforderlich, die Kosten von Vergleichs- und Austauschoperationen zu analysieren, ein Faktor, der wiederum von der Größe der Datensätze und Schlüssel abhängt. Wenn zum Beispiel die Datensätze wie in den obigen Implementationen aus einem Wort bestehende Schlüssel sind, so dürfte ein Austausch (zwei Zugriffe auf das Feld) etwa doppelt so teuer sein wie ein Vergleich. In einer solchen Situation sind die Laufzeiten von Selection Sort und Insertion Sort, grob gesagt, vergleichbar, während Bubble Sort doppelt so viel Zeit benötigt. (Tatsächlich dürfte Bubble Sort unter nahezu allen Umständen halb so schnell sein wie Insertion Sort!) Falls jedoch die Datensätze im Vergleich zu den Schlüsseln groß sind, ist Selection Sort am besten geeignet.

Eigenschaft 8.5 Für Dateien mit großen Datensätzen und kleinen Schlüsseln ist Selection Sort linear.

Nehmen wir an, daß die Kosten für einen Vergleich 1 Zeiteinheit und die Kosten für einen Austausch M Zeiteinheiten betragen. (Dies könnte zum Beispiel der Fall sein, wenn die Datensätze aus M Worten und die Schlüssel aus einem Wort bestehen.) Dann benötigt Selection Sort etwa N2 Zeiteinheiten für Vergleiche und etwa NM Zeiteinheiten für Austauschoperationen, um eine Datei der Größe NM zu sortieren. Falls N = O(M) gilt, ist das eine lineare Funktion der Datenmenge. w.z.b.w.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]