>> MARK Grozen-SMITH: Hallo, ich bin Mark Grozen-Smith, und dies ist Quicksort.
Genau wie Insertion Sort und Bubble Sortieren, Quicksort ist ein Algorithmus zur
Sortieren einer Liste oder eine Reihe von Dingen.
Der Einfachheit halber nehmen wir an, dass diejenigen, Dinge sind nur ganze Zahlen, aber
wissen, dass Quicksort arbeitet für mehr als nur Zahlen.
Quickstart ist ein bisschen komplizierter als Ein-oder Luftblase, aber es ist
auch wesentlich effizienter in den meisten Fällen.
Warten Sie eine Sekunde.
Hat er nur "die meisten sagen, Fällen ", nicht" alle "?
Interessanterweise nicht.
Nicht in allen Fällen die gleichen sind.
Sie nicht über dieses Detail kümmern, wenn Sie nicht O-Notation noch nicht gesehen, aber
Quicksort ist ein O (n-Quadrat)-Algorithmus im schlimmsten Fall, wie
Ein-oder Bubble-Sort.
Allerdings handelt es typischerweise viel mehr wie eine alte analoge m-Algorithmus.
Warum?
Wir kommen wieder zu bekommen, dass später.
Aber jetzt wollen wir nur lernen wie Quicksort funktioniert.
>> Lassen Sie uns also über diese Quicksorting gehen Array von ganzen Zahlen von der kleinsten
zum größten.
Hier haben wir die Zahlen 6, 5, 1, 3, 8, 4, 7, 9 und 2.
Zuerst wählen wir das letzte Element der dieses Array - in diesem Fall zwei -
und rufen, dass die "Pivot". Als nächstes wir beginnen, an zwei Dinge sehen -
ein, dem niedrigsten Index, der ich entnehmen so bleiben rechts
die Wand, und zwei, die am weitesten links Element, das ich die "aktuelle nennen
Element. "Was wir tun werden, ist schauen alle anderen Elemente, andere
als die Dreh, und legte all die Elemente kleiner ist als der Schwenk die
links von der Wand und alle, größer als der Schwenk die
rechts von der Wand.
Dann, endlich, wir werden die Dreh Drop direkt auf die Wand, um sie zwischen setzen
alle Zahlen kleiner als und alle Zahlen größer.
>> Also lassen Sie uns das tun.
Nehmen Sie die 2, legen Sie die Wand in die Anfang, und rufen Sie die 6 den "aktuellen
Element. "So wollen wir zu sehen unsere aktuellen Element, der 6.
Und da es größer als die 2, lassen wir es dort zu den
rechts von der Wand.
Dann bewegen wir uns auf in der 5 aussehen wie unsere aktuelle Element und sehen, dass diese
ist wiederum größer als der Schwenk, deswegen lassen, wo es ist auf der rechten
Seite der Wand.
Wir ziehen weiter.
Unsere aktuelle Element Jetzt 1 und - oh.
Das ist jetzt anders.
Das aktuelle Element ist jetzt kleiner als der Dreh, so wollen es uns
auf der linken Seite der Wand.
Um dies zu tun, lass uns einfach wechseln die aktuelle Element mit dem niedrigsten Index
sitzt nur auf der rechten Seite der Wand.
Nun, die Wand bis ein Index bewegen wir uns so dass der 1 auf der linken Seite
Seite jetzt der Wand.
>> Warten.
Ich habe gerade die Elemente auf die gemischt rechten Seite der Wand, oder nicht?
Mach dir keine Sorgen.
Das ist in Ordnung.
Das einzige, was wir interessieren uns für jetzt ist, dass alle diese Elemente in der
rechts von der Wand sind größer als der Drehpunkt.
Keine tatsächliche Reihenfolge wird noch angenommen.
>> Nun, zurück zu sortieren.
Also wir suchen weiter der Rest der Elemente.
Und in diesem Fall sieht man, dass es keine weiteren Elemente weniger als die
Pivot, sie alle so weiter verlassen wir die rechte Seite der Wand.
Schließlich, um das aktuelle Element erhalten wir und dass es die Schwenk.
Nun bedeutet, dass wir zwei haben Abschnitte der Anordnung, wobei die erste
klein auf dem Drehzapfen und auf der linken Seite von der Wand und dem zweiten Wesen
größer als der Schwenk die rechten Seite der Wand.
Wir wollen das Drehelement zwischen setzen die beiden, und dann werden wir wissen,
daß die Schwenk in seiner richtigen Abschluss sortierten Ort.
So schalten wir das erste Element auf der rechten Seite der Wand mit der Schwenk,
und wir wissen, ist die Schwenk in der rechten Position.
>> Dann wiederholen wir diesen Vorgang für die Teilfelder links und rechts des Schwenk.
Seit der letzten Unterfeld ist nur ein Element lange wissen wir, dass es schon
sortierten denn wie kann man aus sein bestellen, wenn Sie nur ein Element sind?
Für die rechte Seite des Sub-Array, wir sehen, dass die Dreh ist 5 und die Wand
ist nur der 6 übrig.
Und auch das aktuelle Element startet als 6.
So 6 größer als 5 ist.
Wir überlassen es wo es auf die rechten Seite der Wand.
Nun fortfahren, 3 kleiner als 5 ist.
So schalten wir es mit dem ersten Element nur rechts von der Wand.
Nun zog ich die Wand nach oben ein.
Nun bewegt auf den 8.
8 ist größer als 5, und so lassen wir es.
Die 4 ist kleiner als 5, so dass wir sie umschalten.
Und an.
>> Jedes Mal, wenn wir uns wiederholen Sie den Vorgang auf der linken und rechten Seite der Anordnung. wir
wählen Sie einen Drehpunkt und machen die Vergleiche und erstellen Sie eine weitere Ebene der links und
rechten Untergruppen.
Diese rekursiven Aufruf wird bis weiter wir das Ende erreichen, wenn wir haben
die Gesamt Array aufgeteilt in nur Sub-Arrays der Länge 1.
Von dort wissen wir, das Array sortiert da jedes Element zumin
Irgendwann, ein Drehpunkt.
Mit anderen Worten, für jedes Element, die alle Die Zahlen auf der linken Seite sind geringere
Werte und alle Zahlen auf die Recht haben größere Werte.
>> Diese Methode funktioniert sehr gut, wenn die Wert der gewählten Dreh ist
etwa in der Mitte Bereich der Listenwerte.
Dies würde bedeuten, dass nach dem wir uns bewegen Elemente herum, es etwa so viele
Elemente auf der linken Seite des Schwenk wie es auf der rechten Seite.
Und die Teile-und-Herrsche-Natur der Quicksort-Algorithmus wird dann genommen
vollen Nutzen aus.
Dies schafft eine Laufzeit von O (n log n) die n, weil wir zu tun haben, n minus 1
Vergleiche, die auf jeder Generation und Protokoll n, denn wir haben, um die Liste zu teilen
log n mal.
In den schlimmsten Fällen, diese Algorithmus tatsächlich sein kann O (n
Quadrat.) Angenommen auf jeder Generation der Dreh passiert einfach so zu sein das
kleinste oder der größte der Zahlen wir Sortierung.
Dies würde bedeuten, den Abbau der Liste n-mal und machen n minus 1
Vergleiche jede einzelne Zeit.
So o n quadriert.
>> Wie können wir die Methode?
Eine gute Möglichkeit, um das Verfahren zu verbessern, ist um auf die Wahrscheinlichkeit reduzieren, dass
die Laufzeit ist eigentlich immer o n quadriert.
Merken schlimmsten schlimmsten Fall kann nur geschehen, wenn die
Dreh gewählt ist immer die höchste oder niedrigsten Wert im Array.
Um dies zu gewährleisten ist es weniger wahrscheinlich passieren, können wir die Dreh durch finden
Auswahl mehrerer Elemente und unter dem Medianwert.
>> Mein Name ist Mark Grozen-Smith, und dies ist CS50.
>> Der Einfachheit halber nehmen wir an, dass diejenigen, Dinge sind nur ganze Zahlen, aber
wissen, dass QUICKSERT -
QUICKSERT?
Entschuldigung.
>> Hier haben wir die ganzen Zahlen 6, 5, 1, 3, 8, 4, 9.
>> Sprecher 1: Wirklich?
>> Sprecher 2: Hören Sie nicht dort.
>> Sprecher 1: Wirklich?