Sortieren Ii

Transcript

Sortieren II Tobias Pr¨oger 20. Oktober (vorl¨ aufige Fassung 0 vom 19. Oktober 2016) Erkl¨ arung: Diese Mitschrift ist als Erg¨ anzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollst¨ andigkeit 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 Schl¨ ussels. Wenn wir also das Maximum effizienter bestimmen k¨onnten, dann erg¨abe sich ein Sortierverfahren, das mit weniger als quadratischer Zeit auskommt. Der im Folgenden vorgestellte Heap erlaubt die Extraktion des maximalen Schl¨ ussels in Zeit O(log n), wenn n Schl¨ ussel verwaltet werden. Heaps Ein Array A[1..n] mit n Schl¨ usseln 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) erf¨ ullen. Obwohl ein Max-Heap intern als Array gespeichert wird, kann er als bin¨ arer Baum visualisiert werden, wobei jeder Schl¨ ussel 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 f¨ ur einen Knoten mit Schl¨ ussel x die Schl¨ ussel der entsprechenden Nachfolger h¨ochstens so gross wie x selbst sind. Folglich ist der maximale Schl¨ ussel 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 bin¨arer Baum. Der Index rechts neben einem Knoten mit Schl¨ ussel k entspricht der Position von k im Array A. W¨ahrend das reine Auslesen des maximalen Schl¨ ussels 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 Schl¨ ussel nach A[1] kopiert. Abb. 2.3: Wiederherstellung der Heap-Eigenschaft f¨ ur die in Abbildung 2.2 dargestellte Struktur. Zun¨achst werden die Schl¨ ussel 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 l¨ osen das Problem wie folgt. Sei m eine Variable, die die Anzahl der Elemente eines Heaps A[1..m] speichert. Wir speichern zu extrahierenden Schl¨ ussel A[1], kopieren den in A[m] gespeicherten Schl¨ ussel 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 Schl¨ ussel ist gr¨ osser als die Schl¨ ussel der Nachfolger). Daher wird der in der Wurzel gespeicherte Schl¨ ussel mit dem gr¨ osseren der an den beiden Nachfolgern gespeicherten Schl¨ ussel vertauscht. Somit ist die Heap-Eigenschaft an der Wurzel erf¨ ullt, kann aber am entsprechenden Nachfolger verletzt sein. Folglich wird genau dort die Heap-Eigenschaft auf die gleiche Art wiederhergestellt, und die Wiederherstellung wird f¨ ur die jeweiligen Nachfolger fortgesetzt, bis A[1..m] wieder ein Heap ist. Man beachte, dass die Heap-Eigenschaft jeweils nur f¨ ur den Nachfolger w1 wiederhergestellt werden muss, dessen Schl¨ ussel mit dem Schl¨ ussel des jeweiligen Vorg¨angers v vertauscht wurde. F¨ ur den anderen Nachfolger w2 (sofern existent) ist die Heap-Eigenschaft sowieso erf¨ ullt, weil in dem unter w2 gespeicherten Teilbaum u ussel ¨berhaupt keine Schl¨ ver¨ andert wurden, und weil der in w1 vorher gespeicherte Schl¨ ussel gr¨osser als der in w2 gespeicherte Schl¨ ussel 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 gr¨ osserer Nachfolger 5 if A[i] < A[j] then Vertausche A[i] und A[j]; i ← j 6 else return . Heap-Bed. erf¨ ullt: Abbruch Theorem 1. Sei A[i..m] mit 1 ≤ i < m ein Array, sodass die Heap-Eigenschaft f¨ ur alle Positionen k ∈ {i + 1, . . . , m} gilt (d.h., sie ist h¨ ochstens 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 f¨ ur alle Positionen k ∈ {i, . . . , m}. Wiederherstellung des Heaps Laufzeit und Korrektheit Beweis. Wir haben bereits im Vorfeld argumentiert, dass der Algorithmus tats¨ achlich nicht nur die Heap-Eigenschaft an der Position i, sondern f¨ ur alle Positionen i, i + 1, . . . , m wiederherstellt. Die Laufzeit ist proportional zur Anzahl der Schleifendurchl¨aufe, denn in den Schritten 2–6 werden nur konstant viele Operationen ausgef¨ uhrt. 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 sp¨ atestens, 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)) Schleifendurchl¨aufe. 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 Schl¨ usseln A[1], . . . , A[n] effizient ein Heap zu dieser Schl¨ usselmenge erstellt werden kann. Wir beobachten zun¨achst, dass f¨ ur die Positionen bn/2c + 1, . . . , n die Heap-Eigenschaft sofort gilt (anschaulich gesprochen besitzen diese keine Nachfolgerknoten und k¨onnen als Heaps mit genau einem Element interpretiert werden). F¨ ur die Position bn/2c muss aber die Heap-Eigenschaft nicht notwendigerweise erf¨ ullt sein. Wir rufen nun f¨ ur 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 f¨ ur alle k ∈ {i + 1, . . . , n}, und nach Theorem (1) gilt nach Terminierung des Aufrufs die Heap-Eigenschaft f¨ ur 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 f¨ ur 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 ausgef¨ uhrt. 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) f¨ ur eine geeignete Konstante C > 0. Wir m¨ ussen 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 zun¨achst aus, dass f¨ ur 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 Absch¨atzung (∗) gilt wegen dn/2e Y i=1 StirlingAbsch¨ atzung  i≥ dn/2e e dn/2e ≥  n dn/2e 2e , und diese wiederum gilt aufgrund der Stirling-Absch¨ atzung  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 zun¨ achst 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) Schl¨ usselvergleiche und -vertauschungen durchgef¨ uhrt. Beweis. Nach der Terminierung der Schleife in Schritt 1 ist A[1..n] wegen Theorem (2) ein Max-Heap. F¨ ur die Schleife in Schritt 3 zeigen wir 4 nun die folgende Invariante: Nach genau i ∈ {0, . . . , n − 1} Schleifendurchl¨ aufen ist A[1..n − i] ein Max-Heap, und f¨ ur jedes j ∈ {1, . . . , i} enth¨alt A[n − j + 1] das j-gr¨ osste 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 g¨ ultig, 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 f¨ ur jedes j ∈ {1, . . . , i} enth¨alt A[n − j + 1] das j-gr¨ osste Element. Das (n − i + 1)-gr¨osste 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 f¨ ur jedes j ∈ {1, . . . , i + 1} das j-gr¨ osste Element in A[n − j + 1] gespeichert. Der Heap erstreckt sich nun u ¨ber die Positionen A[1..m − 1], und nur f¨ ur 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 beschr¨ ankt. 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 f¨ uhrt zu folgender Idee f¨ ur ein Sortierverfahren: Die Folge A[1], . . . , A[n] wird in die zwei ann¨ ahernd 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 L¨ange n zusammengef¨ ugt. Wir zeigen zun¨ achst, 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 n¨achste Element von F , und der Zeiger i wird um 1 erh¨ oht. Ansonsten wird F2 [j] das n¨achste Element von F , und j wird um 1 erh¨ oht. Dieses Vorgehen wird wiederholt, bis entweder F1 oder F2 vollst¨ andig durchlaufen sind. Danach wird die noch nicht ersch¨opfte Folge komplett an das Ende von F geh¨ angt. 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 zun¨achst in einem 5 Hilfsarray B der L¨ ange 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 ersch¨ opft 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 ersch¨ opft ist, h¨ ange sie hinten an while i ≤ middle do B[k] ← A[i]; i ← i + 1; k ← k + 1 8 . Falls die zweite Teilfolge noch nicht ersch¨ opft ist, h¨ ange sie hinten an while j ≤ right do B[k] ← A[j]; j ← j + 1; k ← k + 1 9 . Kopiere Inhalte von B nach A zur¨ uck 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 zun¨achst induktiv die folgende Aussage: Nach k Durchl¨ aufen 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 L¨ange 0 und die Aussage gilt trivialerweise. (!) Induktionsannahme: Sei nach k Durchl¨aufen 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 erh¨oht, 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 ausgef¨ uhrt. Sei o.B.d.A. i ≤ middle. Dann ist nach k Durchl¨aufen der Schleife im dritten Schritt B[k] ≤ A[i], und da A[i..middle] sortiert ist, k¨ onnen die verbleibenden Elemente von A[i..middle] an das Ende von B geh¨ angt 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) Schl¨ usselbewegungen und Vergleiche ausgef¨ uhrt. Laufzeit Beweis. Der Aufwand zur Initialisierung des Arrays der Gr¨osse (right − left + 1) im ersten Schritt betr¨ agt Θ(right − left). Die Schleifen in den Schritten 3 und 9 werden Θ(right − left) Mal durchlaufen, die Schleifen in den Schritten 7 und 8 nur h¨ ochstens O(right − left) Mal. Da f¨ ur alle anderen Schritte nur Zeit O(1) anf¨allt, ergibt sich eine Gesamtlaufzeit von Θ(right − left). In jedem Durchlauf der Schleife in Schritt 3 wird genau ein Schl¨ usselvergleich ausgef¨ uhrt. Ausserdem wird jedes Element genau einmal nach B und genau einmal zur¨ uck nach A kopiert. Damit betr¨agt die Anzahl der Schl¨ usselbewegungen 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 H¨ alfte von A Sortiere hintere H¨ alfte von A Verschmilz Teilfolgen Theorem 6. Sei A[1..n] ein Array. Der Aufruf von Mergesort(A, 1, n) sortiert A und ben¨ otigt in jedem Fall Θ(n log n) viele Schl¨ usselbewegungen und Vergleiche. Beweis. F¨ ur den Nachweis der Korrektheit von Mergesort benutzen wir verallgemeinerte Induktion u ¨ber die Arraygr¨osse n. Induktionsverankerung (n = 1): Arrays der L¨ange 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 h¨ ochstens 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 h¨ ochstens 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 ann¨ahernd gleich langer Teilfolgen mit Gesamtl¨ ange n werden nach Lemma 5 Θ(n) Schl¨ usselvergleiche ben¨otigt. F¨ ur ein Array der L¨ ange 1 werden C(1) = Θ(1) viele Schl¨ ussel verglichen, und allgemein ben¨ otigt Mergesort zum Sortieren von n Elementen l n m j n k C(n) = C +C + Θ(n) ∈ Θ(n log n) (9) 2 2 Schl¨ usselvergleiche. Die ersten beiden Summanden beschreiben die von den rekursiven Aufrufen (in den Schritten 3 und 4) ben¨otigten Schl¨ usselvergleiche, und Θ(n) ist die zur Verschmelzung der sortierten Teilfolgen ben¨ otigten Vergleiche. Die oben beschriebene Anzahl an Schl¨ usselvergleichen gilt in jedem Fall, damit ergibt sich Cmin (n) = Cavg (n) = Cmax (n) ∈ Θ(n log n). (10) Analog betr¨ agt die Anzahl der Schl¨ usselbewegungen Mmin (n) = Mavg (n) = Mmax (n) ∈ Θ(n log n), (11) da nach Lemma 5 beim Verschmelzen zweier Folgen mit Gesamtl¨ange n auch Θ(n) viele Schl¨ ussel bewegt werden. Reines 2-Wege-Mergesort Ist n = 2k eine Zweierpotenz, dann verschmilzt rekursives Mergesort zum Sortieren von A[1..n] zun¨ achst alle Teilfolgen der L¨ange 1, danach alle Teilfolgen der L¨ange 2, danach alle Teilfolgen der L¨ange 4 usw. Reines 2-Wege-Mergesort greift diese Idee (auch f¨ ur 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 L¨ ange 2k−1 werden zu einer sortierten Folge der L¨ange 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 L¨ ange der sortierten Teilfolgen, und die gesamte Folge ist sortiert, wenn in einem Durchlauf nur noch zwei Teilfolgen verschmolzen werden m¨ ussen. 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 . L¨ ange bereits sortierter Teilfolgen . Verschmilz Folgen d. L¨ ange 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 L¨ ange der Teilfolgen Theorem 7. Sei A[1..n] ein Array. Der Aufruf von StraightMergesort(A) sortiert A und ben¨ otigt in jedem Fall Θ(n log n) viele Schl¨ usselbewegungen und Vergleiche. 8 Nat¨ urliches 2-Wege-Mergesort Nat¨ urliches 2-Wege-Mergesort vermeidet wie reines 2-Wege-Mergesort rekursive Aufrufe, beginnt aber initial mit der Verschmelzung von m¨oglichst langen bereits sortierte Teilfolgen, w¨ ahrend reines 2-Wege-Mergesort immer mit sortierten Folgen der L¨ange 1 beginnt. Das zu sortierende Array A bestehe nun aus k l¨angsten bereits sortierten Teilfolgen (sog. Runs) R1 , . . . , Rk . Ein neuer Run beginnt also genau dann, wenn ein kleinerer Schl¨ ussel auf einen gr¨osseren folgt. Nat¨ urliches 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 n¨ achsten 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 vergr¨ ossern 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 vergr¨ ossern 12 Merge(A, left, middle, right) 13 else right ← n . Es gibt keinen zweiten Run 14 until left = 1 Theorem 8. Der Algorithmus NaturalMergesort f¨ uhrt Laufzeit (a) im besten Fall keine Schl¨ usselbewegungen und n − 1 Vergleiche, (b) im durchschnittlichen sowie im schlechtesten Fall Θ(n log n) Schl¨ usselbewegungen 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 f¨ ur 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 Schl¨ ussel bewegt, und die Anzahl der Vergleiche betr¨agt 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 Nat¨ urliches 2-WegeMergesort (12) Zur Analyse des durchschnittlichen Falls u ¨berlegen wir zun¨achst, dass eine zuf¨ allige Permutation von n Schl¨ usseln im Mittel n/2 Runs enth¨ alt: F¨ ur zwei benachbarte Schl¨ ussel ki und ki+1 ist die Wahrscheinlichkeit f¨ ur ki < ki+1 genauso gross wie f¨ ur 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 ben¨otigen Cavg (n) ∈ Θ(n log n) und Mavg (n) ∈ Θ(n log n) Vergleiche bzw. Schl¨ usselbewegungen. 10 (13)