[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.