[PYTHON] Tri rapide sans utiliser le tri
Bonsoir! (^^)! Hier essayant d'endormir l'enfant Je me suis endormi tel quel (rires).
Maintenant, trions par ordre croissant avec un tri rapide. C'était une autre idée intéressante. Cette fois, nous utiliserons while. J'ai écrit un simple gars comme critique.
test.py
x = 10
pc = 5
# x >S'il s'agit d'un PC, allez à l'intérieur et exécutez le processus
# !(x > pc)Si, l'instruction while est réussie!
while x > pc:
x -= 1
print(x)
print("result is ",x)
Comme vous pouvez le voir, tant que x> pc, il tourne en rond dans l'instruction while. X = x -1 est exécuté à chaque fois. Après cela, quand x = 6, je le mets dans l'instruction while, Puisque x- = 1 est défini dans le traitement à l'intérieur, la relation x> pc est rompue car x = 5 est défini. Dans le processus suivant, vous devez quitter l'instruction while. .. Au cas où, je publierai le résultat de l'exécution.
Résultat d'exécution.py
9
8
7
6
5
result is 5
D'après ce qui précède, le miso de l'instruction while est aussi long qu'il correspond à l'instruction conditionnelle. Le fait est que le processus peut être répété.
Pourquoi l'utilisez-vous? Voilà l'histoire. Entrons dans le sujet principal (Rappelez-vous que le temps reviendra plus tard).
Cette fois, nous utiliserons ce tableau X.
Quelle que soit la valeur au centre de ce tableau, je voudrais trier par celui-ci.
?? ?? ?? À quoi vous comparez-vous? ?? ??
Oui je suis désolé.
Comparez la valeur la plus à gauche avec la valeur médiane.
Pour le moment, 1 contre 5 Évidemment, la valeur médiane de 5 est plus grande.
Ensuite.
8 contre 5! C'est évidemment plus grand que 8.
Oui Stop !!.
C'est la fin de la recherche d'une valeur supérieure à la valeur médiane de la première étape.
La deuxième étape consiste à trouver ** inférieur à la médiane ** à partir du bord droit.
Alors partons de la fin.
5 vs. 9 !
Rester c'est bien. Suivant!
5 vs. 3 !
La médiane est plus grande, n'est-ce pas?
C'est bon. J'ai trouvé.
L'étape 2 est terminée.
L'étape suivante consiste à inverser les valeurs trouvées respectivement à l'étape 1 et à l'étape 2.
- Étape 1: Trouvez une valeur ** supérieure à la médiane
- Étape 2: Trouvez une valeur ** inférieure à la médiane
L'image est ici.
J'ai fait un déficit après le changement, mais qu'en est-il?
Tu peux le trier comme ça, c'est important, ambiance (rires)
Alors que faites-vous ensuite?
Répétez les étapes 1 et 2. Cependant, Lptr + = 1, Rptr- = 1.
Oui, essayez de vous rapprocher de la médiane et répétez la même chose.
????Pourquoi?
Eh bien, faisons-le.
Plus précisément, X [2] contre X [4] et X [4] contre X [6].
X [2] vs X [4] est du bingo, mais dans le cas de X [4] vs X [6]
Maintenant que X [4] <X [6] tient, exécutez X [4] vs X [** 5 **] suivant.
Maintenant il est temps d'échanger (rires)
Toutes les valeurs à gauche de la valeur médiane de 5 sont inférieures à 5.
Un tableau supérieur à 5 est complété à droite de la médiane.
Laissons le mouvement jusqu'à présent dans le code. Par exemple, la valeur qui va du côté gauche par la médiane est x [Lptr], Qu'en est-il de x [Rptr] comme argument qui va du côté droit par la valeur médiane?
- Lptr = Pointeur gauche / Rptr = Pointeur droit Pas de sens (rires)!?
test.py
#Tableau
x = [1,8,7,4,5,2,6,3,9]
#Pointeur central
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
# x[Lptr]Le pointeur Lptr s'incrémente tant qu'il est inférieur à la médiane
while x[Lptr] < x[cen]:
Lptr += 1
# x[Rptr]Le pointeur Rptr est un décrément tant qu'il est supérieur à la médiane
while x[cen] < x[Rptr]:
Rptr -= 1
#Juste au cas où, Lptr<Déclenché pour être Rptr
if Lptr < Rptr:
#Retourner la valeur
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
Lançons-le.
#Avant l'exécution
#[1,8,7,4,5,2,6,3,9]
#Après exécution
[1,3,7,4,5,2,6,8,9]
Ça? 3 et 8 juste retournés (rires) Vraiment.
Recherche de valeurs supérieures / inférieures à la médiane Vous ne pouvez exprimer le travail de retournement qu'une seule fois dans ce qui précède. Si la description ci-dessus est tant que Lptr <Rptr, tant que cette relation est maintenue Il répète la description ci-dessus (rappelez-vous! Explication de tout au début !!).
test.py
x = [1,8,7,4,5,2,6,3,9]
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
#Position du pointeur Lptr<Tant que vous maintenez la relation Rptr
#Continue de traiter le contenu de while.
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]
#Lorsque le travail de retournement est terminé, effectuez le travail suivant
#Commençons la prochaine comparaison.
Lptr += 1
Rptr -= 1
print(x)
Le résultat de l'exécution est le suivant.
Résultat d'exécution.py
#Avant l'exécution
#[1,8,7,4,5,2,6,3,9]
[1,3,2,4,5,7,6,8,9]
Ouais! (^^)! Moins de 5 à gauche de la médiane 5 La valeur à droite de la valeur médiane 5 était supérieure à 5 (* ´ 艸 ｀) Que faire? Suivant (rires)
Tout d'abord, après avoir effectué le traitement ci-dessus Où sont arrivés Lptr et Rptr?
test.py
while Lptr < Rptr:
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
Puisque Lptr + = 1 lorsque Lptr = 3, Lptr = 4 Lorsque Rptr = 5, Rptr- = 1, donc Rptr = 4 Lptr = Rptr = 4, et Lptr <Rptr, qui était la condition de l'instruction while, est devenu Cela le cassera, alors quittez l'instruction while. Juste au cas où, faisons-le.
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 4 Rptr = 4
Je vois. Pour le moment, faisons un diagramme.
Que diriez-vous d'un petit Izil supplémentaire comme ci-dessous?
test.py
x = [1,8,7,4,5,2,6,3,9]
cen = len(x)//2
Lptr = 0
Rptr = len(x)-1
#↓ "="Ajouter!!
while Lptr <= Rptr: # Lptr ==Rptr entre également dans le processus à l'intérieur tandis que
#Le while suivant est ignoré.
#<===d'ici
while x[Lptr] < x[cen]:Lptr += 1
while x[cen] < x[Rptr]:Rptr -= 1
#<==Jusque là
# Lptr ==Rptr entre également dans le processus à l'intérieur tandis que
#↓ "="Ajouter!!
if Lptr <= Rptr:
#x[4],x[4] = x[4],x[4]Si inoffensif
x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
#C'est important!!Incrémenter et décrémenter respectivement!
Lptr += 1
Rptr -= 1
print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
"=" A été ajouté à certaines parties. En conséquence, le résultat de l'exécution sera le suivant.
Résultat d'exécution.py
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 5 Rptr = 3
Les positions de Lptr et Rptr ont été inversées.
Ensuite, le tableau x donné dans cet état,
Région 1: x [0] ~ Rptr (= x [3])
Zone 2: Lptr (= x [5]) ~ x [8]
Que se passe-t-il si je les divise et que j'effectue le même traitement qu'auparavant?
Oui, c'est récursif.
On dirait que quelque chose va naître!? (Rires)
J'ai changé la description pour rendre la récurrence plus facile à utiliser.
test.py
#left :Le plus à gauche comme valeur initiale
#right:Tout à fait à droite comme valeur initiale
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]
#Tableau à utiliser x
#La valeur initiale de left est l'extrémité gauche, entrez donc 0
#Puisque la valeur initiale de right est la bonne extrémité, len(x)-Entrez 1
quick_sort(x,0,len(x)-1)
L'image de la récurrence est désormais la suivante.
Zone avec gauche, Rptr comme gauche, droite (vert),
La zone (bleue) où Lptr et droite sont à gauche et à droite semble bouger.
Et une telle description?
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}")
#À gauche comme indiqué dans la figure ci-dessus<Si la relation de Rptr est établie
#Trier la zone de gauche de manière récursive
if left < Rptr:
quick_sort(x,left,Rptr)
#Lptr comme indiqué dans la figure ci-dessus<Si la bonne relation tient
#Trier la bonne zone de manière récursive
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)
Le résultat de l'exécution est ici.
[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
Si vous regardez la dernière ligne, elle est triée. Que dois-je faire pour expliquer les progrès (; ´ ･ ω ･)
Recommended Posts