[Powered by Google Translate] TOMMY: Werfen wir einen Blick auf Auswahl sortieren, ein Algorithmus für die Aufnahme einer Liste von Zahlen und sortieren. Ein Algorithmus, erinnern, ist einfach eine Schritt-für-Schritt Verfahren zur Durchführung einer Aufgabe. Die Grundidee Auswahl Art ist zu teilen unserer Liste in zwei Teile - eine sortierte Abschnitt und einen unsortierten Teil. Bei jedem Schritt des Algorithmus wird eine Rufnummer aus dem bewegten unsortierten Abschnitt zu dem Abschnitt sortiert bis schließlich die gesamte Liste sortiert ist. Also hier ist eine Liste von sechs Nummern - 23, 42, 4, 16, 8 und 15. Gerade jetzt die gesamte Liste wird als unsortiert. Auch wenn eine Reihe wie 16 bereits in seiner korrekten sein Lage hat unser Algorithmus nicht wissen, dass bis zum gesamte Liste sortiert ist. So wir betrachten jede Zahl zu unsortiert bis wir sortieren es selbst gemacht. Wir wissen, dass wir die Liste in aufsteigender Reihenfolge sein wollen. Also werden wir aufbauen wollen die sortierte Teil unserer Liste von links nach rechts, vom kleinsten zum größten. Um dies zu tun, brauchen wir, um die minimale unsortierten Element zu finden und ihn am Ende der sortierten Abschnitts. Da diese Liste nicht sortiert ist, ist der einzige Weg, das zu tun, um Blick auf jedes Element in der unsortierten Teil, erinnern welches Element ist die niedrigste und Vergleichen jedes Element dazu. Also werden wir zunächst an der 23 aussehen. Dies ist das erste Element, das wir gesehen haben, so dass wir daran erinnern, es als das Minimum. Als nächstes werden wir bei 42 aussehen. 42 ist größer als 23, so ist immer noch die 23 Minimum. Weiter ist die 4, die weniger als 23 ist, so dass wir 4 erinnern als neue Minimum. Weiter ist 16, die größer als 4 ist, also 4 noch das Minimum. 8 ist größer als 4 und 15 ist größer als 4, so muß 4 der kleinste unsortierten Element. Also auch wenn wir als Menschen können sofort sehen, dass 4 ist das kleinste Element, muss unser Algorithmus zu betrachten jeden unsortierten Element, selbst nachdem wir die 4 gefunden - die kleinste Element. So, jetzt haben wir das kleinste Element, 4 gefunden, wir möchten um es in der sortierten Teil der Liste zu verschieben. Da dies der erste Schritt, bedeutet dies, wir wollen 4 bei setzen der Anfang der Liste. Gerade jetzt 23 steht am Anfang der Liste, so wir tauschen die 4 und die 23. So, jetzt unsere Liste sieht wie folgt aus. Wir wissen, dass 4 muss an seinem endgültigen Standort sein, denn es ist sowohl das kleinste Element und das Element am Anfang der Liste. Dies bedeutet also, dass wir nicht immer müssen es wieder zu bewegen. Also lasst uns diesen Vorgang wiederholen, um ein weiteres Element, um das Add sortierten Teil der Liste. Wir wissen, dass wir nicht brauchen, um an der 4 aussehen, weil es bereits sortiert. So können wir auf die 42 zu starten, was wir als die erinnern kleinste Element. Also das nächste wir an der 23, die weniger als 42 ist zu sehen, so dass wir Speichern 23 ist das neue Minimum. Weiter sehen wir die 16, die weniger als 23 ist, so 16 ist das neue Minimum. Nun auf 8, die weniger als 16 ist zu sehen, so dass 8 ist das neue Minimum. Und schließlich 8 weniger als 15, so wissen wir, dass 8 ein Minimum ist unsortierten Element. Das heißt also, wir sollten 8 bis sortierten anhängen Teil der Liste. Gerade jetzt 4 ist die einzige sortiert Element, so wollen wir platzieren die 8 neben dem 4. Da 42 ist das erste Element in dem Teil des unsortierten Liste, wir wollen die 42 und die 8 tauschen. So, jetzt unsere Liste sieht wie folgt aus. 4 und 8 stellen die sortierte Teils der Liste, und das restlichen Zahlen stellen den unsortierten Teil der Liste. Lassen Sie uns also mit einer anderen Iteration fortsetzen. Wir beginnen mit 23 dieses Mal, da brauchen wir nicht zu sehen die 4 und die 8 nicht mehr, weil sie haben bereits sortiert. 16 ist kleiner als 23, so dass wir daran erinnern, 16 als neue Minimum. 16 ist kleiner als 42, aber weniger als 15 16, 15 muß so die minimale unsortierten Element. So, jetzt wollen wir die 15 und die 23 zu tauschen uns diese Liste. Die sortierte Teil der Liste besteht aus 4, 8 und 15, und diese Elemente sind immer noch unsortiert. Aber es passiert einfach so, dass die nächste unsortierten Element 16, bereits sortiert. Allerdings gibt es keine Möglichkeit für unser Algorithmus zu wissen, dass 16 ist bereits in die richtige Position, so müssen wir noch wiederholen exakt den gleichen Prozess. Wir sehen, dass weniger als 16 42 ist, und 16 ist kleiner als 23, so 16 muss das kleinste Element sein. Es ist unmöglich, dieses Element mit sich selbst tauschen, so können wir lassen Sie es einfach in dieser Lage. Also brauchen wir noch ein Pass von unserem Algorithmus. 42 ist größer als 23, so 23 muss das sein minimale unsortierten Element. Sobald wir tauschen die 23 und die 42, haben wir am Ende mit unserem letzten sortierte Liste - 4, 8, 15, 16, 23, 42. Wir wissen, 42 muss an der richtigen Stelle zu sein, da es das ist einzige Element links, und das ist Auswahl sort. Lassen Sie uns nun zu formalisieren unser Algorithmus mit einigen Pseudocode. On line ein, können wir sehen, dass wir die Integration über brauchen jedes Element der Liste. Außer dem letzten Element, da die 1-Element Liste bereits sortiert. Auf Leitung zwei, betrachten wir das erste Element des unsortierten Teil der Liste, um das Minimum sein, wie wir mit unseren getan Beispielsweise, so haben wir etwas zu vergleichen. Zeile drei beginnt eine zweite Schleife, in denen wir iterieren Jede unsortierten Element. Wir wissen, dass, nachdem ich Iterationen, die sortierte Teil unserer Liste muss i Elemente in ihr, da jeder Schritt Arten aus einem Element. Also der erste unsortierten Element muss in der Position i plus 1 sein. On line vier, vergleichen wir das aktuelle Element auf das Minimum Element, das wir bisher gesehen haben. Wenn das aktuelle Element kleiner ist als die minimale Element, dann erinnern wir uns das aktuelle Element als neue minimale on line fünf. Schließlich auf Leitungen sechs und sieben, tauschen wir die minimale Element mit dem ersten Element unsortierter, wodurch Zugabe zu dem sortierten Teil der Liste. Sobald wir einen Algorithmus haben, eine wichtige Frage stellen uns als Programmierer ist, wie lange hat das gedauert? Wir werden zuerst die Frage stellen, wie lange dauert es, bis dieser Vorgang Algorithmus im schlimmsten Fall laufen? Erinnern wir uns stellen diese Lauf Zeit mit O-Notation. Um die minimale unsortierten Elementes zu bestimmen, haben wir hatte im Wesentlichen um jedes Element in der Liste zu vergleichen jedes andere Element in der Liste. Intuitiv, das klingt wie ein O n squared Betrieb. Mit Blick auf unsere Pseudocode, haben wir auch eine Schleife verschachtelt Inneren eine weitere Schleife, die tatsächlich klingt wie ein O von n quadrierten Betrieb. Beachten Sie jedoch, dass wir nicht brauchen, um über die aussehen gesamte Liste bei der Bestimmung der minimalen unsortierten Element? Sobald wir wussten, dass die 4 sortiert wurde, zum Beispiel, haben wir nicht müssen noch einmal anschauen. So funktioniert das untere die Laufzeit? Für unsere Liste der Länge 6, mussten wir fünf machen Vergleiche für das erste Element, vier Vergleiche für das zweite Element, und so weiter. Das bedeutet, dass die Gesamtzahl der Schritte ist die Summe von die ganzen Zahlen von 1 bis zur Länge der Liste minus 1 ist. Wir können dies mit einer Summierung darstellen. Wir werden nicht in Summen hier. Es zeigt sich aber, dass diese Summierung gleich n mal ist n minus 1 über 2. Oder äquivalent, n quadriert über 2 minus n über 2. Wenn man über die asymptotische Laufzeit dieses n quadrierten Terms wird dieses n Begriff dominieren. So Auswahl Art ist O n Quadrat. Daran erinnern, dass in unserem Beispiel, Auswahl sort noch erforderlich, um prüfen, ob eine Zahl, die bereits sortiert wurde benötigt, um bewegt werden. Das heißt also, dass, wenn wir liefen Auswahl sort über eine bereits sortierten Liste, würde es erfordern die gleiche Anzahl von Schritten, wie sie wäre beim Lauf über eine völlig unsortierte Liste. So Auswahl Art hat eine best case Leistung von n squared, denen wir vertreten mit Omega n Quadrat. Und das ist es für die Auswahl sort. Nur eine der vielen Algorithmen können wir verwenden, um eine Liste zu sortieren. Mein Name ist Tommy, und dies ist CS50.