Sortieren II

Sortieren II
Tobias Pröger
20. Oktober (vorläufige Fassung 0 vom 19. Oktober 2016)
Erklärung: Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen
Anspruch auf Vollständigkeit und Korrektheit. Wir sind froh über Hinweise zu Fehlern oder
Ungenauigkeiten. Bitte senden Sie diese an [email protected].
1
Heapsort
Wir erinnern uns kurz an Sortieren durch Auswahl. Die quadratische Laufzeit dieses
Verfahrens ergab sich aus der linearen Laufzeit zur Bestimmung des maximalen
Schlüssels. Wenn wir also das Maximum effizienter bestimmen könnten, dann ergäbe
sich ein Sortierverfahren, das mit weniger als quadratischer Zeit auskommt. Der im
Folgenden vorgestellte Heap erlaubt die Extraktion des maximalen Schlüssels in Zeit
O(log n), wenn n Schlüssel verwaltet werden.
Heaps Ein Array A[1..n] mit n Schlüsseln heisst Max-Heap, wenn alle Positionen
k ∈ {1, . . . , n} die Heap-Eigenschaft
(2k ≤ m) ⇒ (A[k] ≥ A[2k]) und (2k + 1 ≤ m) ⇒ (A[k] ≥ A[2k + 1])
(1)
erfüllen. Obwohl ein Max-Heap intern als Array gespeichert wird, kann er als binärer
Baum visualisiert werden, wobei jeder Schlüssel in genau einem Knoten gespeichert
wird (vgl. Abbildung 2.1). Wir beobachten, dass die Nachfolger(knoten) des in A an
Position k gespeicherten Knotens im Array an den Positionen 2k sowie 2k +1 gespeichert sind, sofern diese existieren. Die Heap-Eigenschaft besagt damit anschaulich,
dass für einen Knoten mit Schlüssel x die Schlüssel der entsprechenden Nachfolger
höchstens so gross wie x selbst sind. Folglich ist der maximale Schlüssel des Heaps
in A[1] bzw. im obersten Knoten gespeichert. Weiterhin sehen wir, dass jeder unter
einem Knoten gespeicherte Teilbaum ebenfalls als Heap interpretiert werden kann.
Max-Heap
HeapEigenschaft
Auslesen des
Maximums
Abb. 2.1: Darstellung des Max-Heaps A = h9, 6, 7, 3, 4, 5, 2, 1i als binärer
Baum. Der Index rechts neben einem Knoten mit Schlüssel k entspricht
der Position von k im Array A.
Während das reine Auslesen des maximalen Schlüssels also einfach ist, ist nicht offensichtlich, wie er effizient aus dem Heap extrahiert (d.h. entfernt) werden kann.
Das Problem liegt in der starren, durch das Array implizit vorgegebenen Struktur
1
Extraktion des
Maximums
Abb. 2.2: Extraktion des Maximums (Wert 9) in dem in Abbildung
2.1 dargestellten Heaps. Im ersten Schritt wird der in A[8] gespeicherte
Schlüssel nach A[1] kopiert.
Abb. 2.3: Wiederherstellung der Heap-Eigenschaft für die in Abbildung
2.2 dargestellte Struktur. Zunächst werden die Schlüssel 1 und 7 vertauscht, danach 1 und 5.
Abb. 2.4: Der rekonstruierte Heap A = h7, 6, 5, 3, 4, 1, 2i.
des Heaps. Wir lösen das Problem wie folgt. Sei m eine Variable, die die Anzahl der
Elemente eines Heaps A[1..m] speichert. Wir speichern zu extrahierenden Schlüssel
A[1], kopieren den in A[m] gespeicherten Schlüssel nach A[1] und verringern den
Wert von m um 1. Nun aber ist A[1..m] im Allgemeinen kein Heap mehr, denn
an der Wurzel ist die Heap-Eigenschaft verletzt (der dort gespeicherte Schlüssel ist
grösser als die Schlüssel der Nachfolger). Daher wird der in der Wurzel gespeicherte
Schlüssel mit dem grösseren der an den beiden Nachfolgern gespeicherten Schlüssel
vertauscht. Somit ist die Heap-Eigenschaft an der Wurzel erfüllt, kann aber am entsprechenden Nachfolger verletzt sein. Folglich wird genau dort die Heap-Eigenschaft
auf die gleiche Art wiederhergestellt, und die Wiederherstellung wird für die jeweiligen Nachfolger fortgesetzt, bis A[1..m] wieder ein Heap ist. Man beachte, dass die
Heap-Eigenschaft jeweils nur für den Nachfolger w1 wiederhergestellt werden muss,
dessen Schlüssel mit dem Schlüssel des jeweiligen Vorgängers v vertauscht wurde.
Für den anderen Nachfolger w2 (sofern existent) ist die Heap-Eigenschaft sowieso erfüllt, weil in dem unter w2 gespeicherten Teilbaum überhaupt keine Schlüssel
verändert wurden, und weil der in w1 vorher gespeicherte Schlüssel grösser als der
in w2 gespeicherte Schlüssel ist.
2
Restore-Heap-Condition(A, i, m)
1 while 2 ∗ i ≤ m do
. A[i] hat linken Nachfolger
2
j ←2∗i
. A[j] ist linker Nachfolger
3
if j + 1 ≤ m then
. A[i] hat rechten Nachfolger
4
if A[j] < A[j + 1] then j ← j + 1
. A[j] ist grösserer Nachfolger
5
if A[i] < A[j] then Vertausche A[i] und A[j]; i ← j
6
else return
. Heap-Bed. erfüllt: Abbruch
Theorem 1. Sei A[i..m] mit 1 ≤ i < m ein Array, sodass die Heap-Eigenschaft für
alle Positionen k ∈ {i + 1, . . . , m} gilt (d.h., sie ist höchstens bei i verletzt). Die
Laufzeit von Restore-Heap-Condition(A, i, m) ist O(log(m/i)), und nach der
Terminierung gilt die Heap-Eigenschaft für alle Positionen k ∈ {i, . . . , m}.
Wiederherstellung des
Heaps
Laufzeit und
Korrektheit
Beweis. Wir haben bereits im Vorfeld argumentiert, dass der Algorithmus tatsächlich nicht nur die Heap-Eigenschaft an der Position i, sondern für alle Positionen i, i + 1, . . . , m wiederherstellt. Die Laufzeit ist
proportional zur Anzahl der Schleifendurchläufe, denn in den Schritten
2–6 werden nur konstant viele Operationen ausgeführt. Sei f (k) der Wert
der Variablen i vor dem k-ten Durchlauf der Schleife. In den Schritten
2–4 wird der Wert von i mindestens verdopppelt, also sind
f (0) = i und f (k) ≥ 2f (k − 1).
(2)
Man kann leicht induktiv zeigen, dass f (k) ≥ i2k−1 . Die Schleife terminiert spätestens, wenn die Variable i den Wert m erreicht. Wir erhalten
i2k−1 ≤ f (k) ≤ m ⇒ 2k−1 ≤
m
⇒ k − 1 ≤ log(m/i),
i
(3)
also gibt es maximal k ∈ O(log(m/i)) Schleifendurchläufe.
Erzeugung eines Heaps Im vorigen Abschnitt wurde gezeigt, wie das maximale Element effizient aus dem Heap extrahiert werden kann. Es verbleibt zu zeigen,
wie aus einer Menge von n Schlüsseln A[1], . . . , A[n] effizient ein Heap zu dieser
Schlüsselmenge erstellt werden kann. Wir beobachten zunächst, dass für die Positionen bn/2c + 1, . . . , n die Heap-Eigenschaft sofort gilt (anschaulich gesprochen
besitzen diese keine Nachfolgerknoten und können als Heaps mit genau einem Element interpretiert werden). Für die Position bn/2c muss aber die Heap-Eigenschaft
nicht notwendigerweise erfüllt sein. Wir rufen nun für i ∈ {bn/2c, . . . , 1} sukzessive den Algorithmus Restore-Heap-Condition(A, i, n) auf. Vor dem Aufruf der
Methode mit Parameter i galt die Heap-Eigenschaft für alle k ∈ {i + 1, . . . , n}, und
nach Theorem (1) gilt nach Terminierung des Aufrufs die Heap-Eigenschaft für alle
k ∈ {i, . . . , n}. Folglich ist nach dem letzten Aufruf mit dem Parameter i = 1 das
Array A[1..n] ein Max-Heap.
Theorem 2. Sei A[1..n] ein Array. Wird für i = bn/2c, . . . , 1 sukzessive der Algorithmus Restore-Heap-Condition(A, i, n) aufgerufen, dann ist A[1..n] ein MaxHeap. Dabei werden insgesamt nur Θ(n) Operationen ausgeführt.
3
Laufzeit und
Korrektheit
Beweis. Die Korrektheit des Vorgehens wurde bereits im Vorfeld gezeigt. Die Aussage der Laufzeit ist ein wenig trickreicher. Der Aufruf von
Restore-Heap-Condition(A, i, n) hat eine Laufzeit von C log(n/i) für
eine geeignete Konstante C > 0. Wir müssen also
bn/2c
X
bn/2c
C log(n/i) = C
X
i=1
log(n/i) ∈ Θ(n)
(4)
i=1
zeigen. Dazu nutzen wir zunächst aus, dass für k positive Zahlen a1 , . . . , ak
k
X
k
Y
log(ai ) = log
i=1
!
(5)
ai
i=1
gilt. Nun erhalten wir
bn/2c
dn/2e
X
X
log(n/i) ≤
i=1
i=1

Y n
 = log
log(n/i) = log 
i

dn/2e
i=1
ndn/2e
Qdn/2e
i=1
!
i
(∗)
≤ log (2e)dn/2e = dn/2e log(2e) ∈ Θ(n).
(6)
Dabei ist e ≈ 2.71828 die Eulersche Zahl. Die Abschätzung (∗) gilt wegen
dn/2e
Y
i=1
StirlingAbschätzung
i≥
dn/2e
e
dn/2e
≥
n dn/2e
2e
,
und diese wiederum gilt aufgrund der Stirling-Abschätzung
n n
n n √
n! ≥
2πn ≥
.
e
e
(7)
(8)
Heapsort Sei A[1..n] das zu sortierende Array. Zur Sortierung von A benutzen wir
nun zunächst das im vorigen Abschnitt vorgestellte Verfahren zur Erzeugung eines
Heaps aus A, und danach extrahieren wir n − 1 Mal das Maximum aus dem Heap.
Heapsort
Heapsort(A)
1 for i ← bn/2c downto 1 do
2
Restore-Heap-Condition(A, i, n)
3 for m ← n downto 2 do
4
Vertausche A[1] und A[m]
5
Restore-Heap-Condition(A, 1, m − 1)
Laufzeit und
Korrektheit
Theorem 3. Sei A[1..n] ein Array. Der Algorithmus Heapsort sortiert A; dabei
werden maximal O(n log n) Schlüsselvergleiche und -vertauschungen durchgeführt.
Beweis. Nach der Terminierung der Schleife in Schritt 1 ist A[1..n] wegen Theorem (2) ein Max-Heap. Für die Schleife in Schritt 3 zeigen wir
4
nun die folgende Invariante: Nach genau i ∈ {0, . . . , n − 1} Schleifendurchläufen ist A[1..n − i] ein Max-Heap, und für jedes j ∈ {1, . . . , i}
enthält A[n − j + 1] das j-grösste Element.
Induktionsverankerung (i = 0): Die Invariante gilt vor dem ersten
Schleifendurchlauf, da A[1..n] wie gesehen ein Max-Heap ist.
Induktionsannahme: Angenommen, die Invariante ist gültig, nachdem
die Schleife genau i Mal durchlaufen wurde.
Induktionsschluss (i → i + 1): Im (i + 1)-ten Schleifendurchlauf gilt
offenbar m = n−i. Nach Induktionsannahme ist zu Beginn dieses Durchlaufs A[1..n − i] ein Max-Heap, und für jedes j ∈ {1, . . . , i} enthält
A[n − j + 1] das j-grösste Element. Das (n − i + 1)-grösste Element
ist also in derzeit A[1] gespeichert, und durch die Vertauschung mit
A[m] = A[n − i] in Schritt 4 ist am Ende des Durchlaufs für jedes
j ∈ {1, . . . , i + 1} das j-grösste Element in A[n − j + 1] gespeichert.
Der Heap erstreckt sich nun über die Positionen A[1..m − 1], und nur
für die Position 1 kann die Heap-Bedingung verletzt sein. Nach Theorem
(1) wird diese in Schritt 5 aber wiederhergestellt, also gilt die Invariante
auch am Ende des (i + 1)-ten Schleifendurchlaufs.
Nach der Terminierung des Algorithmus ist A[1..n] also sortiert, und
wegen den Theoremen (1) und (2) ist die Gesamtlaufzeit durch O(log n)
nach oben beschränkt.
2
Mergesort
Idee Schon beim Maximum-Subarray-Problem haben wir gesehen, dass Divideand-Conquer helfen kann, die Laufzeit eines Algorithmus zu verbessern. Dieses Prinzip des rekursiven Aufteilens führt zu folgender Idee für ein Sortierverfahren: Die Folge A[1], . . . , A[n] wird in die zwei annähernd gleich grossen Teilfolgen A[1], . . . , A[bn/2c]
sowie A[bn/2c + 1], . . . , A[n] aufgeteilt, die rekursiv sortiert werden. Nach der Sortierung der Teilfolgen werden diese wieder zu einer sortierten Gesamtfolge der Länge
n zusammengefügt. Wir zeigen zunächst, wie diese Verschmelzung sortierter Teilfolgen realisiert werden kann. Danach beschreiben wir Sortierverfahren, die bereits
sortierte Teilfolgen verschmelzen und so eine insgesamt sortierte Folge erzeugen.
Verschmelzen sortierter Teilfolgen Seien F1 und F2 zwei sortierte Teilfolgen. Die
sortierte Gesamtfolge F wird erzeugt, indem F1 und F2 mit zwei Zeigern von vorn
nach hinten durchlaufen werden. Dies geschieht mithilfe von zwei Variablen i und
j, die wir mit 1 initialisieren. Ist F1 [i] < F2 [j], dann wird F1 [i] das nächste Element
von F , und der Zeiger i wird um 1 erhöht. Ansonsten wird F2 [j] das nächste Element
von F , und j wird um 1 erhöht. Dieses Vorgehen wird wiederholt, bis entweder F1
oder F2 vollständig durchlaufen sind. Danach wird die noch nicht erschöpfte Folge
komplett an das Ende von F gehängt.
Der im Folgenden vorgestellte Algorithmus Merge realisiert die Verschmelzung
zweier bereits sortierter Teilfolgen. Diesem Algorithmus werden die vier Parameter
A, left, middle und right übergeben. Dabei findet sich die bereits sortierte Teilfolge
F1 in A[left..middle] und F2 in A[middle + 1..right]. Die verschmolzene Folge F soll
schliesslich in A[left..right] gespeichert werden. Da dies genau die Positionen in A
sind, an denen F1 und F2 gespeichert sind, muss die sortierte Folge zunächst in einem
5
Hilfsarray B der Länge right−left+1 gespeichert werden. Die Inhalte von B werden
dann im letzten Schritt auf die entsprechenden Positionen im Array A kopiert.
Verschmelzen
der Teilfolgen
Merge(A, left, middle, right)
1 B ← new Array[right-left+1]
. Hilfsarray zum Verschmelzen
2 i ← left; j ← middle+1; k ← 1
. Zeiger zum Durchlaufen
3 . Wiederhole, solange beide Teilfolgen noch nicht erschöpft sind
while (i ≤ middle) and (j ≤ right) do
4
if A[i] ≤ A[j] then B[k] ← A[i]; i ← i + 1
5
else B[k] ← A[j]; j ← j + 1
6
k ←k+1
7 . Falls die erste Teilfolge noch nicht erschöpft ist, hänge sie hinten an
while i ≤ middle do B[k] ← A[i]; i ← i + 1; k ← k + 1
8 . Falls die zweite Teilfolge noch nicht erschöpft ist, hänge sie hinten an
while j ≤ right do B[k] ← A[j]; j ← j + 1; k ← k + 1
9 . Kopiere Inhalte von B nach A zurück
for k ← left to right do A[k] ← B[k − left + 1]
Korrektheit
Lemma 4. Seien A[1..n] ein Array, 1 ≤ left ≤ middle ≤ right ≤ n und sowohl
A[left..middle] als auch A[middle + 1..right] bereits sortiert. Nach dem Aufruf von
Merge(A, left, middle, right) ist A[left..right] komplett sortiert.
Beweis. Wir zeigen zunächst induktiv die folgende Aussage: Nach k
Durchläufen der Schleife in Schritt 3 ist B[1..k] sortiert, und es sind
B[k] ≤ A[i], falls i ≤ middle, sowie B[k] ≤ A[j], falls j ≤ right.
Induktionsverankerung (k = 0): Vor dem ersten Schleifendurchlauf
ist B[1..0] ein Array der Länge 0 und die Aussage gilt trivialerweise. (!)
Induktionsannahme: Sei nach k Durchläufen der Schleife B[1..k] sortiert, und B[k] ≤ A[i], falls i ≤ middle, sowie B[k] ≤ A[j], falls j ≤ right.
Induktionsschluss (k → k + 1): Betrachte den (k + 1)-ten Durchlauf
der Schleife in Schritt 3. Es seien o.B.d.A. A[i] ≤ A[j], i ≤ middle und
j ≤ right. Nach Induktionsannahme ist B[1..k] sortiert, und B[k] ≤ A[i].
Wird also B[k+1] ← A[i] gesetzt, dann ist B[1..k+1] noch immer sortiert,
und B[k+1] = A[i] ≤ A[i+1], falls (i+1) ≤ middle, sowie B[k+1] ≤ A[j],
falls j ≤ right. Anschliessend werden sowohl i als auch k um 1 erhöht,
also gilt die Aussage auch nach dem (k + 1)-ten Schleifendurchlauf. Der
Fall A[j] < A[i] wird analog bewiesen.
Nach der Terminierung der Schleife in Schritt 3 gilt entweder i >
middle oder j > right. Also wird genau eine der Schleifen in den Schritten
7 und 8 ausgeführt. Sei o.B.d.A. i ≤ middle. Dann ist nach k Durchläufen
der Schleife im dritten Schritt B[k] ≤ A[i], und da A[i..middle] sortiert
ist, können die verbleibenden Elemente von A[i..middle] an das Ende von
B gehängt werden, und nach Schritt 8 ist B[1..(right − left + 1)] komplett
sortiert.
6
Lemma 5. Seien A[1..n] ein Array, 1 ≤ left < right ≤ n, middle = b(left + right)/2c
und sowohl A[left..middle] als auch A[middle + 1..right] bereits sortiert. Im Aufruf
von Merge(A, left, middle, right) werden Θ(right − left) Schlüsselbewegungen und
Vergleiche ausgeführt.
Laufzeit
Beweis. Der Aufwand zur Initialisierung des Arrays der Grösse (right −
left + 1) im ersten Schritt beträgt Θ(right − left). Die Schleifen in den
Schritten 3 und 9 werden Θ(right − left) Mal durchlaufen, die Schleifen
in den Schritten 7 und 8 nur höchstens O(right − left) Mal. Da für alle
anderen Schritte nur Zeit O(1) anfällt, ergibt sich eine Gesamtlaufzeit
von Θ(right − left). In jedem Durchlauf der Schleife in Schritt 3 wird
genau ein Schlüsselvergleich ausgeführt. Ausserdem wird jedes Element
genau einmal nach B und genau einmal zurück nach A kopiert. Damit
beträgt die Anzahl der Schlüsselbewegungen und Vergleiche ebenfalls
Θ(right − left).
Rekursives 2-Wege-Mergesort
Der im letzten Abschnitt vorgestellte Algorithmus zur Verschmelzung zweier sortierter Teilfolgen kann nun benutzt werden, um ein Array rekursiv zu sortieren. Dem
im Folgenden vorgestellten Algorithmus Mergesort werden die drei Parameter A,
left und right übergeben, und die Aufgabe besteht in der Sortierung des Teilarrays
A[left..right]. Zur Sortierung des gesamten Arrays A[1..n] wird dann Mergesort(A,
1, n) aufgerufen.
Mergesort(A, left, right)
Rekursives
Mergesort
1 if left < right then
2
middle ← b(left + right)/2c
3
Mergesort(A, left, middle)
4
Mergesort(A, middle+1, right)
5
Merge(A, left, middle, right)
.
.
.
.
Mittlere Position
Sortiere vordere Hälfte von A
Sortiere hintere Hälfte von A
Verschmilz Teilfolgen
Theorem 6. Sei A[1..n] ein Array. Der Aufruf von Mergesort(A, 1, n) sortiert
A und benötigt in jedem Fall Θ(n log n) viele Schlüsselbewegungen und Vergleiche.
Beweis. Für den Nachweis der Korrektheit von Mergesort benutzen
wir verallgemeinerte Induktion über die Arraygrösse n.
Induktionsverankerung (n = 1): Arrays der Länge 1 sind bereits sortiert. Mergesort terminiert direkt, da die Parameter left und right den
gleichen Wert haben.
Induktionsannahme: Wir nehmen an, dass alle Arrays mit höchstens
n Elementen korrekt sortiert werden.
Induktionsschluss (n → n + 1): Betrachte ein Array mit n + 1 Elementen. Es ist left < right, damit sind A[left..middle] sowie A[middle +
1..right] Arrays mit höchstens n Elementen. Diese werden nach Induktionsvoraussetzung korrekt sortiert. Nach Lemma 4 werden diese sortierten Teilarrays so verschmolzen, dass A[1..n + 1] sortiert ist.
7
Laufzeit und
Korrektheit
Zum Verschmelzen zweier annähernd gleich langer Teilfolgen mit Gesamtlänge n werden nach Lemma 5 Θ(n) Schlüsselvergleiche benötigt.
Für ein Array der Länge 1 werden C(1) = Θ(1) viele Schlüssel verglichen,
und allgemein benötigt Mergesort zum Sortieren von n Elementen
l n m
j n k
C(n) = C
+C
+ Θ(n) ∈ Θ(n log n)
(9)
2
2
Schlüsselvergleiche. Die ersten beiden Summanden beschreiben die von
den rekursiven Aufrufen (in den Schritten 3 und 4) benötigten Schlüsselvergleiche, und Θ(n) ist die zur Verschmelzung der sortierten Teilfolgen
benötigten Vergleiche. Die oben beschriebene Anzahl an Schlüsselvergleichen gilt in jedem Fall, damit ergibt sich
Cmin (n) = Cavg (n) = Cmax (n) ∈ Θ(n log n).
(10)
Analog beträgt die Anzahl der Schlüsselbewegungen
Mmin (n) = Mavg (n) = Mmax (n) ∈ Θ(n log n),
(11)
da nach Lemma 5 beim Verschmelzen zweier Folgen mit Gesamtlänge n
auch Θ(n) viele Schlüssel bewegt werden.
Reines 2-Wege-Mergesort
Ist n = 2k eine Zweierpotenz, dann verschmilzt rekursives Mergesort zum Sortieren
von A[1..n] zunächst alle Teilfolgen der Länge 1, danach alle Teilfolgen der Länge 2,
danach alle Teilfolgen der Länge 4 usw. Reines 2-Wege-Mergesort greift diese Idee
(auch für allgemeine n) auf, vermeidet dabei aber die rekursiven Aufrufe. Im k-ten
Durchlauf wird das Array von links nach rechts durchlaufen, und je zwei Folgen
der Länge 2k−1 werden zu einer sortierten Folge der Länge 2k verschmolzen. Eine
Ausnahme bildet die Folge am rechten Rand des Arrays: Ist n keine Potenz von 2,
dann kann sie weniger als 2k−1 Elemente besitzen (und die Verschmelzung mit einer
anderen Teilfolge weniger als 2k Elemente). In jedem Durchlauf verdoppelt sich also
die Länge der sortierten Teilfolgen, und die gesamte Folge ist sortiert, wenn in einem
Durchlauf nur noch zwei Teilfolgen verschmolzen werden müssen.
Reines 2-WegeMergesort
Laufzeit und
Korrektheit
StraightMergesort(A)
1 length ← 1
2 while length < n do
3
right ← 0
4
while right+length < n do
5
left ← right+1
6
middle ← left+length−1
7
right ← min(middle+length, n)
8
Merge(A, left, middle, right)
9
length ← length∗2
. Länge bereits sortierter Teilfolgen
. Verschmilz Folgen d. Länge length
. A[1..right] ist abgearbeitet
. Es gibt noch mind. zwei Teilfolgen
. Linker Rand der ersten Teilfolge
. Rechter Rand der ersten Teilfolge
. Rechter Rand der zweite Teilfolge
. Verschmilz beide Teilfolgen
. Verdoppelte Länge der Teilfolgen
Theorem 7. Sei A[1..n] ein Array. Der Aufruf von StraightMergesort(A) sortiert A und benötigt in jedem Fall Θ(n log n) viele Schlüsselbewegungen und Vergleiche.
8
Natürliches 2-Wege-Mergesort
Natürliches 2-Wege-Mergesort vermeidet wie reines 2-Wege-Mergesort rekursive Aufrufe, beginnt aber initial mit der Verschmelzung von möglichst langen bereits sortierte Teilfolgen, während reines 2-Wege-Mergesort immer mit sortierten Folgen der
Länge 1 beginnt. Das zu sortierende Array A bestehe nun aus k längsten bereits sortierten Teilfolgen (sog. Runs) R1 , . . . , Rk . Ein neuer Run beginnt also genau dann,
wenn ein kleinerer Schlüssel auf einen grösseren folgt. Natürliches 2-Wege-Mergesort
verschmilzt R1 mit R2 , danach R3 mit R4 usw. Dieses Verfahren wird so lange wiederholt, bis es nur noch einen Run (das sortierte Array A) gibt.
NaturalMergesort(A)
1 repeat
2
right ← 0
. Elemente bis A[right] sind bearbeitet
3
while right < n do
. Finde und verschmilz die nächsten Runs
4
left ← right+1
. Linker Rand des ersten Runs
5
middle ← left
. A[left..middle] ist bereits sortiert
6
while (middle < n) and A[middle + 1] ≥ A[middle] do
7
middle ← middle+1 . Ersten Run um ein Element vergrössern
8
if middle < n then
. Es gibt einen zweiten Run
9
right ← middle+1
. Rechter Rand des zweiten Runs
10
while (right < n) and A[right + 1] ≥ A[right] do
11
right ← right+1
. Zweiten Run um ein Element vergrössern
12
Merge(A, left, middle, right)
13
else right ← n
. Es gibt keinen zweiten Run
14 until left = 1
Theorem 8. Der Algorithmus NaturalMergesort führt
Laufzeit
(a) im besten Fall keine Schlüsselbewegungen und n − 1 Vergleiche,
(b) im durchschnittlichen sowie im schlechtesten Fall Θ(n log n) Schlüsselbewegungen und Θ(n log n) Vergleiche aus.
Beweis.
(a) Im besten Fall ist das Array bereits sortiert, d.h. es besteht nur aus
einem Run. Dann ist A[middle + 1] ≥ A[middle] in Schritt 6 immer
wahr, und die Schleife terminiert für middle = n. Folglich wird in
Schritt 13 right ← n gesetzt, und die Schleife in Schritt 3 terminiert
nach einem Durchlauf. Es werden also keine keine Schlüssel bewegt,
und die Anzahl der Vergleiche beträgt Cmin (n) = n − 1.
(b) Im schlechtesten Fall wird die Schleife im dritten Schritt dlog ne
Mal durchlaufen. Wie beim reinen 2-Wege-Mergesort ergeben sich
damit
Cmax (n) ∈ Θ(n log n) und Mmax (n) ∈ Θ(n log n).
9
Natürliches
2-WegeMergesort
(12)
Zur Analyse des durchschnittlichen Falls überlegen wir zunächst,
dass eine zufällige Permutation von n Schlüsseln im Mittel n/2
Runs enthält: Für zwei benachbarte Schlüssel ki und ki+1 ist die
Wahrscheinlichkeit für ki < ki+1 genauso gross wie für ki > ki+1 ,
also 1/2. Ist ki > ki+1 , dann endet bei ki ein Run. Damit ergeben
sich im durchschnittlichen Fall n/2 Runs, und wir benötigen
Cavg (n) ∈ Θ(n log n) und Mavg (n) ∈ Θ(n log n)
Vergleiche bzw. Schlüsselbewegungen.
10
(13)

Download Report