[Musikwiedergabe] DOUG LLOYD: Auswahl Art ist eine Algorithmus, der, wie man erwarten könnte, sortiert eine Gruppe von Elementen. Und Algorithmus Rückruf ist ein Schritt-für-Schritt-Set von Anweisungen zur Durchführung einer Aufgabe. 

In der Auswahl sortieren Grundidee ist die, finden Sie das kleinste unsortierte Element und es bis zum Ende der sortierten Liste hinzuzufügen. Effektiv, was das bedeutet ist build eine sortierte Liste, ein Element zu einem Zeitpunkt. Zerlegung, um Pseudocode könnten wir diesen Algorithmus angeben wie folgt, wiederholen Sie dies, bis keine unsortierten Elemente bleiben. Suchen Sie in den unsortierten Daten auf den kleinsten Wert zu finden, dann tauschen Sie den kleinsten Wert mit der erste Element der unsortierten Teil. 

Es kann helfen, dies zu visualisieren, so lassen Sie uns einen Blick auf diese. Also das, behaupte ich, ist ein unsortierte Array und ich habe angedeutet durch die anzeigt, dass alle der Elemente sind rot, sie sind noch nicht sortiert. Dies ist die gesamte unsortierten Teil des Arrays. 

Lassen Sie uns also durch die Schritte gehen Auswahl sort, um dieses Array zu sortieren. Also noch einmal, wir werden wiederholen bis keine unsortierten Elemente bleiben. Wir werden Suchen Sie in den Daten auf den kleinsten Wert zu finden, und dann tauschen Sie diesen Wert mit der erste Element der unsortierten Teil. 

Gerade jetzt, wieder die gesamte Array ist der unsortierten Teil. Alle roten Elemente sind unsortiert. So suchen wir durch und finden wir den kleinsten Wert. Wir beginnen am Anfang, Wir gehen bis zum Ende, wir finden, der kleinste Wert ist, ein. Also das ist ein Teil. Und dann Teil zwei, tauschen Sie diesen Wert mit das erste Element des unsortierten Teil, oder die erste rot-Element. 

In diesem Fall wäre das fünf, so tauschen wir ein und fünf. Wenn wir das tun, können wir visuell sehen, dass wir bewegt den kleinsten Wert Element des Arrays, an den Anfang. Effektiv Sortier dieses Element. 

Und so haben wir in der Tat bestätigen, und erklären, dass man, sortiert ist. Und so werden wir den Teil, sortiert anzuzeigen der unser Angebot, indem es Färbung blau. 

Jetzt müssen wir nur den Vorgang wiederholen. Wir suchen durch die unsortierten Teil das Array, das kleinste Element zu finden. In diesem Fall ist es zwei. 

Wir tauschen, dass mit dem ersten Element der unsortierten Teil. In diesem Fall geschieht, zwei auch zu sein das erste Element des unsortierten Teil. Also haben wir tauschen zwei mit sich selbst, was eigentlich nur zwei Blätter wo es ist, und es ist, sortiert. Weiter auf, durchsuchen wir um das kleinste Element zu finden. Es ist drei. Wir tauschen Sie es mit dem ersten Element, das fünf ist. Und jetzt drei sortiert ist. 

Wir suchen wieder durch, und wir Finde das kleinste Element ist vier. Wir tauschen es mit dem ersten Element des unsortierten Teil, und jetzt vier sortiert ist. 

Wir finden, dass fünf ist das kleinste Element. Wir tauschen Sie es mit dem ersten Element der unsortierten Teil. Und nun fünf sortiert ist. 

Und dann endlich unseren unsortierten Teil besteht von nur einem einzelnen Element, so dass wir durchsuchen und wir finden, dass sechs der am kleinsten, und in der Tat nur Element. Und dann können wir feststellen, dass es sortiert ist. Und jetzt haben wir unser Angebot eingeschaltet davor komplett unsortiert in rot, um vollständig sortiert in blau, mit Auswahl sort. 

Also, was ist das schlimmste Szenario hier? Nun, in der absolute worst Fall, müssen wir schauen über alle Elemente des Arrays finden Sie das kleinste unsortierte Element, und wir haben zu wiederholen, dieser Vorgang n-mal. Einmal für jedes Element des Arrays weil nur wir in diesem Algorithmus, Art ein Element zur Zeit. 

Was ist der beste-Case-Szenario? Nun, es ist genau das gleiche, oder? Wir haben tatsächlich immer noch durch Schritt Jedes einzelne Element des Arrays um zu bestätigen, dass es sich, in der Tat, das kleinste Element. 

Also das Worst-Case-Laufzeit, die wir haben, ein Verfahren zu n-mal zu wiederholen, einmal für jede der n Elemente. Und im besten Fall, Wir haben das gleiche zu tun. 

So denken zurück zu unserem Rechenkomplexität Toolbox was glauben Sie, ist das Schlimmste, Bei der Laufzeit für die Auswahl sortieren? Was denken Sie ist der beste Bei der Laufzeit für die Auswahl sortieren? 

Haben Sie erraten, Big O n quadriert, und Big Omega von n quadriert? Sie würden Recht haben. Diejenigen sind, in der Tat, die Worst-Case und Best Case Lauf Zeiten, für die Auswahl sortieren. 

Ich bin Doug Lloyd. Dies ist CS50.