Pivotwahl bei Quicksort und Quickselect?
Guten Abend,
ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben
Aufgabe 1
Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)
.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.
b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.
Aufgabe 2
Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen
Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.
LG
Jensek81
1 Antwort
Es gibt verschiedene Quicksorts - zum Stack greift man bei nicht rekursiver Variante. Swaps macht man allgemein bei Sortierung inplace.
Soweit so gut erstmal.
Im besten Fall teilt Dein Pivot die Eingabemenge beim Paritionieren in zwei gleich große Teilarrays, das sichert Dir die minimale Rekursionstiefe zu. (kürzeste Laufzeit).
----
Du sollst jetzt im Prinzip die Wahrscheinlichkeit dafür berechnen, daß Deine Pivotwahl einen Split erzeugt, der nicht schlechter als 1/4 zu 3/4 ist, heißt das größere Array soll nicht größer als 3/4 der Elemente sein, das kleinere nicht kleiner als 1/4 der Elemente.
Das ist also ein rein stochastische Ding - Ziehe ich uniform ein Element, beträgt die Wahrscheinlichkeit dafür, daß es zwischen 1/4 und 3/4 liegt 0.5. Das gilt auch für jedes der 7 Elemente jeweils. Jetzt bleibt die Frage, wie groß ist die Wahrscheinlichkeit, daß genau das 4. kleinste der 7 im gewünschten Intervall ist? (Also im Prinzip das mittlere)
-----
⌈(links+rechts)/2⌉ - es sei links =n und rechts = n+6 - eien Folge der Länge 7. es ist n+n+6=(2n+6)/2=n+3- also das 4. und somit mittlere Element der Folge.
dort packst Du natürlich das kleinste aller Elemente hin (oder das größte, denn dann entsteht beim pivotieren ein Array der Größe n-1 sowie ein leeres.
Nochmal zu 1 a) ein Gedanke:
Das mittlere der 7 Elemente liegt genau dann im Intervall, wenn nicht 4 oder mehr Elemente unterhalb des Intervalls liegen, oder wenn nicht 4 oder mehr Elemente oberhalb des Intervalls liegen.
Danke für die Antwort KarlRansereiIII.
Eine Frage noch zur 1a).
Wenn ich dich richtig versteh, gibt es also 3 zu betrachtende Intervalle bei reinzufälliger Wahl eines Elements
1) Element ist kleiner als Intervall (0, 1/4)
2) Element liegt genau dazwischen ((1/4 + 1), 3/4)
3) Element ist größer als Intervall (3/4, n)
Wir betrachten nun, dass 4 oder mehr Intervalle oberhalb des Intervalls liegen, d.h.
k = 4,5,6,7.
Könnte man dann nicht einfach die Binominalverteilung über dieses Ereignisse bilden, aufsummieren und die Gegenwahrscheinlichkeit bilden.
D.h. (n über k) * p^k * (1 - p)^n-k ? aufsummiert für k = 4 bis 7?
Weil wir den Hinweis bekommen haben, P (falsches Intervall) und P (beide im falschen Intervall) zu berechnen. Die gesuchte Lösung wäre dann 1 - P (Beide im falschen Intervall). Mich verwirrt dieses beide im falschen Intervall. Warum beide? Wir wählen doch nur ein zufälliges Element.
Ja, mir war heute morgen nachm Aufstehen auch noch etwas dazu durch den Kopf gegangen ...
Es fühlt sich definitiv binomial an, das wäre auch die Richtung in die ich gehen würde. Die Frage ist halt genau das richtige zu ermitteln.
gehen wir es mal durch: Es können 6 von sieben außerhalb unseres mittleren Intervalls liegen, das mittlere Element könnte aber immernoch im Intervall oder außerhalb liegen.
Wenn meine Elemente aber sortiert sind und ich das 4. ziehe, aber mindestens 4 Elemente unterhalb von 1/4 n liegen, dann weiß ich, daß mein gezogenes Element außerhalb meines Wunschintervalls liegt. Ebenso bezüglich des anderen Intervalls (also oberhalb).
Wenn ich jetzt aber von dieser (jeweiligen) Wahrscheinlichkeit die Gegenwahrscheinlichkeit bilde, wäre das aber nicht mehr auf mein Wunschintervall beschränkt. (Ich will ja schließlich Element 4 liegt nich oberhalb und nicht unterhalb).
Ich frage mich was mit:
P (beide im falschen Intervall)
gemeint sein soll.
Vielleicht, wenn man beide Seiten getrennt betrachtet. Also einmal das Szenario dass die kleinsten 4 in das größte Intervall fallen, oder den ungekehrten Fal, dass die 4 größten in das kleinste Intervall fallen.
Unser Tutor hat uns zudem verraten, dass die Lösung wohl 85,88 % sein soll.
Darauf würde ich mit der binominalverteilung auch kommen, d.h.
Summe von k = 4 bis 7: (7 über k) * 1/4^k * 3/4^(7-k) = 0,0706
Jetzt dieser komische Zwischenschritt, den ich nicht verstehe:
2 * 0,0706 = 0,1412
Naja, und dann eben über die Gegenwahrscheinlichkeit: 1 - 0,1412 = 85,88 %
Diese 2 * 0,0706 ("Beide im falschen Intervall") verwirrt mich. :/
Also, nochmal:
Wenn mindestens 4 Elemente von 7 unterhalb 1/4 n liegen, dann liegt das mittlere der 7 unterhalb des Intervalls, in dem liegen sollte, wenn alles gut ist.
Das ist, ohne es jetzt gegenzurechnen laut Deiner Aussage: 0.0706.
Oder aber 4 oder mehr Elemente liegen Oberhalb 3/4, das ist nun ebenso 0.0706.
Die Wahrscheinlichkeit, daß also das eine ungünstige Ereignis eintritt, ODER das andere wäre die Summe, also 2*0.0706. Die Gegenwahrscheinlichkeit, also 1-2*0.0706 wäre demnach die Wahrscheinlichkeit für unseren günstigen Fall.
Beide ungünstigen Fälle sind disjunkt - das ist wichtig.
Ok vielen Dank, KarlRansereiIII. Das war genau das, was mir bisher unklar war. EInen schönen Abend noch :)
Natürlich muß das nicht n +1, n+2 usw. sein, sondern es reicht, wenn die Ordnung gewahrt bleibt, also Mitte kleinste Element, rechts daneben das zweitkleinste, dann links das drittkleinste usw. .
Natürlich klappt es genauso gut, wenn das größte, das zweitgrößte ... genommen wird.
Der Grund für die Anordnung ist ceil(), also das Aufrunden.