[PYTHON] Schnelle Sortierung ohne Sortierung
Guten Abend! (^^)! Gestern versucht das Kind einzuschlafen Ich bin so eingeschlafen wie es war (lacht).
Lassen Sie uns nun in aufsteigender Reihenfolge mit schneller Sortierung sortieren. Dies war eine weitere interessante Idee. Dieses Mal werden wir verwenden, während. Ich schrieb einen einfachen Mann als Rezension.
test.py
x = 10
pc = 5
# x >Wenn es sich um einen PC handelt, gehen Sie hinein und führen Sie den Vorgang aus
# !(x > pc)Wenn, ist die while-Anweisung bestanden!
while x > pc:
x -= 1
print(x)
print("result is ",x)
Wie Sie sehen können, geht es in der while-Anweisung rund und rund, solange x> pc. X = x -1 wird jedes Mal ausgeführt. Danach, wenn x = 6, setze ich es in die while-Anweisung, Da x- = 1 in der Verarbeitung im Inneren gesetzt ist, wird die Beziehung von x> pc unterbrochen, weil x = 5 ist. Im nächsten Prozess müssen Sie die while-Anweisung beenden. .. Für alle Fälle werde ich das Ausführungsergebnis veröffentlichen.
Ausführungsergebnis.py
9
8
7
6
5
result is 5
Aus dem Obigen geht hervor, dass das Miso der while-Anweisung so lang ist, wie es der bedingten Anweisung entspricht. Der Punkt ist, dass der Vorgang wiederholt werden kann.
Warum benutzt du das? Das ist die Geschichte. Kommen wir zum Hauptthema (Denken Sie daran, während später auftauchen wird).
Dieses Mal werden wir dieses Array X verwenden.
Was auch immer der Wert in der Mitte dieses Arrays ist, ich möchte nach diesem sortieren.
?? ?? ?? Womit vergleichst du? ?? ??
Ja tut mir leid.
Vergleichen Sie den Wert ganz links mit dem Medianwert.
Derzeit ist 1 vs. 5. Offensichtlich ist der Medianwert von 5 größer.
Dann als nächstes.
8 gegen 5! Dies ist offensichtlich größer als 8.
Ja, hör auf !!.
Dies ist das Ende der Suche nach einem Wert, der größer als der Medianwert des ersten Schritts ist.
Der zweite Schritt funktioniert, um ** weniger als den Median ** vom rechten Rand zu finden.
Dann lass uns vom Ende gehen.
5 vs. 9 !
Aufenthalt ist okay. Nächster!
5 vs. 3 !
Der Median ist größer, nicht wahr?
Es ist in Ordnung. Ich fand.
Schritt 2 ist beendet.
Der nächste Schritt besteht darin, die in Schritt 1 bzw. Schritt 2 gefundenen Werte umzudrehen.
- Schritt 1: Suchen Sie einen Wert **, der größer als der Median ist
- Schritt 2: Suchen Sie einen Wert **, der kleiner als der Median ist
Das Bild ist hier.
Ich habe nach der Änderung ein Defizit gemacht, aber was ist mit?
Sie können es so sortieren, es ist wichtig, Atmosphäre (lacht)
Also, was machst du als nächstes?
Wiederholen Sie Schritt 1 und Schritt 2. Lptr + = 1, Rptr- = 1.
Ja, versuchen Sie, näher an den Median heranzukommen, und wiederholen Sie dasselbe.
????Warum?
Gut, gut, lass es uns tun.
Insbesondere sind sie X [2] gegen X [4] und X [4] gegen X [6].
X [2] gegen X [4] ist Bingo, aber im Fall von X [4] gegen X [6]
Nachdem X [4] <X [6] gilt, führen Sie das folgende X [4] gegen X [** 5 **] aus.
Jetzt ist es Zeit zum Austausch (lacht)
Alle Werte links vom Medianwert von 5 sind kleiner als 5.
Ein Array größer als 5 wird rechts vom Median vervollständigt.
Lassen Sie uns die Bewegung so weit in den Code fallen. Zum Beispiel ist der Wert, der von der linken Seite durch den Medianwert geht, x [Lptr], Was ist mit x [Rptr] als Argument, das vom Medianwert von der rechten Seite ausgeht?
- Lptr = linker Zeiger / Rptr = rechter Zeiger Kein Sinn (lacht) !?
test.py
#Array
x = [1,8,7,4,5,2,6,3,9]
#Zeiger zentrieren
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
# x[Lptr]Der Zeiger Lptr erhöht sich, solange er unter dem Median liegt
while x[Lptr] < x[cen]:
Lptr += 1
# x[Rptr]Der Zeiger Rptr ist ein Dekrement, solange er größer als der Median ist
while x[cen] < x[Rptr]:
Rptr -= 1
#Nur für den Fall, Lptr<Auslöser für Rptr
if Lptr < Rptr:
#Drehen Sie den Wert um
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
Lass es uns laufen.
#Vor der Ausführung
#[1,8,7,4,5,2,6,3,9]
#Nach der Ausführung
[1,3,7,4,5,2,6,8,9]
Das? 3 und 8 sind gerade umgekippt (lacht) Ja wirklich.
Suchen Sie nach Werten, die größer / kleiner als der Median sind Sie können die Arbeit des Umdrehens nur einmal oben ausdrücken. Wenn die obige Beschreibung Lptr <Rptr ist, solange diese Beziehung beibehalten wird Es wiederholt die obige Beschreibung (denken Sie daran! Erklärung von während am Anfang !!).
test.py
x = [1,8,7,4,5,2,6,3,9]
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
#Zeigerposition Lptr<Solange Sie die Rptr-Beziehung beibehalten
#Verarbeitet den Inhalt von while weiter.
while Lptr < Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
if Lptr < Rptr:
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
#Wenn die Umdrehungsarbeiten abgeschlossen sind, führen Sie die folgenden Arbeiten aus
#Beginnen wir mit dem nächsten Vergleich.
Lptr += 1
Rptr -= 1
print(x)
Das Ausführungsergebnis ist wie folgt.
Ausführungsergebnis.py
#Vor der Ausführung
#[1,8,7,4,5,2,6,3,9]
[1,3,2,4,5,7,6,8,9]
Ja! (^^)! Weniger als 5 links vom Median 5 Der Wert auf der rechten Seite des Medianwerts 5 war größer als 5 (* ´ 艸 ｀) Wie geht's? Weiter (lacht)
Zunächst nach Durchführung der obigen Verarbeitung Wo sind Lptr und Rptr angekommen?
test.py
while Lptr < Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
Da Lptr + = 1 ist, wenn Lptr = 3, ist Lptr = 4 Wenn Rptr = 5 ist, ist Rptr- = 1, also Rptr = 4 Lptr = Rptr = 4 und Lptr <Rptr, die die Bedingung der while-Anweisung war, wurden Dies wird es brechen, also beenden Sie die while-Anweisung. Nur für den Fall, lass es uns tun.
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 4 Rptr = 4
Das war's. Lassen Sie uns vorerst ein Diagramm erstellen.
Wie wäre es mit einem zusätzlichen kleinen Izil wie unten?
test.py
x = [1,8,7,4,5,2,6,3,9]
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
#↓ "="Hinzufügen!!
while Lptr <= Rptr: # Lptr ==Rptr tritt währenddessen auch in den Prozess ein
#Die folgende Zeit wird übersprungen.
#<===von hier
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
#<==Bisher
# Lptr ==Rptr tritt währenddessen auch in den Prozess ein
#↓ "="Hinzufügen!!
if Lptr <= Rptr:
#x[4],x[4] = x[4],x[4]So harmlos
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
#Das ist wichtig!!Inkrementieren bzw. Dekrementieren!
Lptr += 1
Rptr -= 1
print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
"=" Wurde einigen Teilen hinzugefügt. Infolgedessen ist das Ausführungsergebnis wie folgt.
Ausführungsergebnis.py
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 5 Rptr = 3
Die Positionen von Lptr und Rptr wurden umgekehrt.
Dann ist das in diesem Zustand angegebene Array x
Region 1: x [0] ~ Rptr (= x [3])
Bereich 2: Lptr (= x [5]) ~ x [8]
Was passiert, wenn ich sie teile und die gleiche Verarbeitung wie zuvor durchführe?
Ja, es ist rekursiv.
Es sieht so aus, als würde etwas geboren werden !? (Lacht)
Ich habe die Beschreibung geändert, um die Verwendung von Wiederholungen zu vereinfachen.
test.py
#left :Ganz links als Anfangswert
#right:Ganz rechts als Anfangswert
def quick_sort(x,left,right):
Lptr = left
Rptr = right
cen = (left+right)//2
while Lptr <= Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
if Lptr <= Rptr:
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
Lptr += 1
Rptr -= 1
print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
if __name__ =="__main__":
x = [1,8,7,4,5,2,6,3,9]
#Array zur Verwendung von x
#Der Anfangswert von left ist das linke Ende. Geben Sie also 0 ein
#Da der Anfangswert von rechts das rechte Ende ist, wird len(x)-Geben Sie 1 ein
quick_sort(x,0,len(x)-1)
Das Bild der Wiederholung von nun an ist wie folgt.
Bereich mit links, Rptr wie links, rechts (grün),
Der Bereich (blau), in dem Lptr und rechts links und rechts sind, scheint sich zu bewegen.
Wie wäre es mit einer solchen Beschreibung?
quick_sort.py
def quick_sort(x,left,right):
Lptr = left
Rptr = right
cen = (left+right)//2
while Lptr <= Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
if Lptr <= Rptr:
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
Lptr += 1
Rptr -= 1
print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
#Links wie in der Abbildung oben gezeigt<Wenn die Beziehung von Rptr hergestellt ist
#Sortieren Sie den linken Bereich rekursiv
if left < Rptr:
quick_sort(x,left,Rptr)
#Lptr wie in der Abbildung oben gezeigt<Wenn die richtige Beziehung gilt
#Sortieren Sie den richtigen Bereich rekursiv
if Lptr < right:
quick_sort(x,Lptr,right)
if __name__ =="__main__":
x = [1,8,7,4,5,2,6,3,9]
quick_sort(x,0,len(x)-1)
Das Ausführungsergebnis ist hier.
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 5 Rptr = 3
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 2 Rptr = 1
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 1 Rptr = -1
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 3 Rptr = 1
[1, 2, 3, 4, 5, 6, 7, 8, 9] Lptr = 6 Rptr = 5
[1, 2, 3, 4, 5, 6, 7, 8, 9] Lptr = 8 Rptr = 6
Wenn Sie sich die letzte Zeile ansehen, ist sie sortiert. Was soll ich tun, um den Fortschritt zu erklären (; ´ ･ ω ･)
Recommended Posts