Python ｜ Tri de la visualisation ｜ Ça fait du bien de voir
Visualisez comment vous triez en Python
Visualisez comment les données sont triées à l'aide de Tkinter de Python
"Je vois!"
C'est un code qui semble l'être.
before
after
Comme le contenu
--Tri rapide --Tri par fusion --Tri sélectif
Sera réalisée. Voici l exemple de code. Créez des classes. Créez ensuite une fonction.
- Classe de contrôleur --Voir la classe
- Classe de tri
Exemple de code
sortSample.py
# =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
#Avec tkinter et minuteries
#Visualisez le tri
# 2020.06.19 ProOJI
# =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
import tkinter
import time
#Taille de la toile
CANVAS_WIDTH = 600
CANVAS_HEIGHT = 400
#Poids au moment du (des) dessin (s)
WAIT = 0
class Sort():
#Type de tri
SELECTION_SORT = 1
QUICK_SORT = 2
MERGE_SORT = 3
def __init__(self, view):
'Génération d'objets à trier'
self.view = view
def start(self, data, method):
'Commencer le tri'
#Définir une liste de données à trier
self.data = data
#Définir le nombre de données à trier
self.num = len(data)
#Initialisation du comptage de comparaison
self.compare_num = 0
#Effectuer le tri selon la méthode
if method == Sort.SELECTION_SORT:
#Sélectionnez l'exécution du tri
self.selection_sort(0, self.num - 1)
elif method == Sort.QUICK_SORT:
#Exécuter un tri rapide
self.quick_sort(0, self.num - 1)
elif method == Sort.MERGE_SORT:
#Préparer la mémoire de travail pour le tri par fusion
self.work = [0] * self.num
#Exécution du tri de fusion
self.merge_sort(0, self.num - 1)
for num in self.data:
print(num)
#Renvoie le nombre de comparaisons
return self.compare_num
def selection_sort(self, left, right):
'Effectuer un tri sélectif'
if left == right:
#Puisqu'il n'y a qu'une seule donnée, le tri se termine
return
#Déterminez temporairement la valeur minimale
min = self.data[left]
i_min = left
#Rechercher la valeur minimale dans la plage de tri
for i in range(left, right + 1):
if min > self.data[i]:
#Mise à jour de la valeur minimale
min = self.data[i]
i_min = i
#Augmenter le nombre de comparaisons
self.compare_num += 1
#Échangez la valeur minimale et les données les plus à gauche
if i_min != left:
#Remplacez seulement si nécessaire
tmp = self.data[left]
self.data[left] = self.data[i_min]
self.data[i_min] = tmp
#Afficher la séquence de données actuelle
self.view.draw_data(self.data)
#Réduisez la plage et sélectionnez à nouveau
self.selection_sort(left + 1, right)
def quick_sort(self, left, right):
'Effectuer un tri rapide'
if left >= right:
#Le tri se termine car le nombre de données est égal ou inférieur à 1
return
#Détermination du pivot
pivot = self.data[left]
i = left
j = right
#Placez les nombres sous le pivot dans la première moitié du tableau,
#Collectez les nombres au-dessus du pivot dans la seconde moitié du tableau
while True:
#Rechercher des nombres au-dessus du pivot à partir de la gauche
while self.data[i] < pivot:
i += 1
#Augmenter le nombre de comparaisons
self.compare_num += 1
#Recherchez les numéros ci-dessous pivot à partir de la droite
while self.data[j] > pivot:
j -= 1
#Augmenter le nombre de comparaisons
self.compare_num += 1
# i >=Devenir j signifie
#Les nombres ci-dessous pivotent sur le côté gauche du tableau
#Que les nombres au-dessus du pivot sont rassemblés sur le côté droit du tableau
if i >= j:
#Le processus de division de l'ensemble est terminé
break
#Échangez les deux numéros que vous avez recherchés
tmp = self.data[i]
self.data[i] = self.data[j]
self.data[j] = tmp
#La recherche reprend à partir du numéro suivant après l'échange
i += 1
j -= 1
#Afficher la séquence de données actuelle
self.view.draw_data(self.data)
#Trier par une plage de petits nombres
self.quick_sort(left, i - 1)
#Trier par une plage de grands nombres
self.quick_sort(j + 1, right)
def merge_sort(self, left, right):
'Effectuer un tri par fusion'
if left == right:
#Puisqu'il n'y a qu'une seule donnée, le tri se termine
return
#Divisez l'ensemble en deux au centre
mid = (left + right) // 2
#Trier les données de chaque ensemble après division
self.merge_sort(left, mid)
self.merge_sort(mid + 1, right)
#Fusionner chaque ensemble trié
self.merge(left, mid, right)
#Afficher la séquence de données actuelle
self.view.draw_data(self.data)
def merge(self, left, mid, right):
'Fusionner des ensembles'
#Définir le point de départ du premier set
i = left
#Définissez le point de départ du deuxième set
j = mid + 1
#Définir le point de départ de l'ensemble de destinations de fusion
k = 0
#L'un des deux ensembles
#Boucle jusqu'à ce que tous soient fusionnés
while i <= mid and j <= right:
#Augmenter le nombre de comparaisons
self.compare_num += 1
#Des deux ensembles sans les données fusionnées
#Fusionner la plus petite des premières données
if (self.data[i] < self.data[j]):
self.work[k] = self.data[i]
#L'index de l'ensemble fusionné et
#Incrémenter l'index de l'ensemble de destination de fusion
i += 1
k += 1
else:
self.work[k] = self.data[j]
#L'index de l'ensemble fusionné et
#Incrémenter l'index de l'ensemble de destination de fusion
j += 1
k += 1
#Un ensemble de données non fusionnées
#Fusionner dans l'ensemble de destinations de fusion
while i <= mid:
#Augmenter le nombre de comparaisons
self.compare_num += 1
self.work[k] = self.data[i]
i += 1
k += 1
while j <= right:
#Augmenter le nombre de comparaisons
self.compare_num += 1
self.work[k] = self.data[j]
j += 1
k += 1
#Copier l'ensemble de destinations de fusion dans les données
j = 0
for i in range(left, right + 1):
self.data[i] = self.work[j]
j += 1
class View():
def __init__(self, master):
'Génération d'objets liés à l'interface utilisateur'
#divers paramètres
self.drawn_obj = []
#Déterminez la taille de la toile
self.canvas_width = CANVAS_WIDTH
self.canvas_height = CANVAS_HEIGHT
#Créer un cadre pour afficher les informations
self.canvas_frame = tkinter.Frame(
master,
)
self.canvas_frame.grid(column=1, row=1)
#Créer un cadre pour le widget d'opération
self.operation_frame = tkinter.Frame(
master,
)
self.operation_frame.grid(column=2, row=1, padx=10)
#Génération et placement de canevas
self.canvas = tkinter.Canvas(
self.canvas_frame,
width=self.canvas_width,
height=self.canvas_height,
)
self.canvas.pack()
#Génération et placement d'étiquettes
self.text = tkinter.StringVar()
self.text.set("Appuyez sur le bouton de démarrage")
self.label = tkinter.Label(
self.canvas_frame,
textvariable=self.text,
)
self.label.pack()
#Génération et organisation de cadres pour le placement de zone de texte
max_w = CANVAS_WIDTH // 2
max_h = CANVAS_HEIGHT // 2
if max_w < max_h:
max = max_w
else:
max = max_h
self.text_frame = tkinter.LabelFrame(
self.operation_frame,
text="Nombre de données (maximum" + str(max) + "）"
)
self.text_frame.pack(ipadx=10, pady=10)
self.entry = tkinter.Entry(
self.text_frame,
width=4
)
self.entry.pack()
#Génération et placement des cadres pour le placement des boutons radio
self.radio_frame = tkinter.LabelFrame(
self.operation_frame,
text="algorithme"
)
self.radio_frame.pack(ipadx=10, pady=10)
#Génération d'objets pour obtenir le bouton coché
self.sort = tkinter.IntVar()
self.sort.set(Sort.QUICK_SORT)
#Créer et placer 3 boutons radio pour la sélection de l'algorithme
self.selection_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="Tri sélectif",
value=Sort.SELECTION_SORT
)
self.selection_button.pack()
self.quick_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="Tri rapide",
value=Sort.QUICK_SORT
)
self.quick_button.pack()
self.merge_button = tkinter.Radiobutton(
self.radio_frame,
variable=self.sort,
text="Tri par fusion",
value=Sort.MERGE_SORT
)
self.merge_button.pack()
#Génération et placement des boutons de démarrage
self.button = tkinter.Button(
self.operation_frame,
text="début",
)
self.button.pack()
def start(self, n):
'Dessiner l'arrière-plan'
#Définir le nombre de données
self.num = n
#Déterminez la largeur de la ligne représentant une donnée
self.line_width = CANVAS_WIDTH / self.num
#Déterminez la hauteur de ligne de la valeur de données 1
#Lorsque la valeur des données est N, la hauteur de la ligne est auto.line_height *Devenir N
self.line_height = CANVAS_HEIGHT / self.num
#Quand il y a trop de données à dessiner
if self.line_width < 2 or self.line_height < 2:
return False
#Pour le réglage de la position de l'arrière-plan (centré)
self.offset_x = int(
(self.canvas.winfo_width() - self.line_width * self.num) / 2
)
self.offset_y = int(
(self.canvas.winfo_height() - self.line_height * self.num + 1) / 2
)
#Supprimer les données une fois dessinées
for obj in self.drawn_obj:
self.canvas.delete(obj)
#Vider la liste de données dessinée car elle a été supprimée
self.drawn_obj = []
#Supprimer l'objet d'arrière-plan à l'avance
self.canvas.delete("background")
#Dessiner l'arrière-plan
self.canvas.create_rectangle(
self.offset_x,
self.offset_y,
int(self.offset_x + self.line_width * self.num),
int(self.offset_y + self.line_height * self.num),
width=0,
fill="#EEEEFF",
tag="background"
)
#Refléter immédiatement le dessin
self.canvas.update()
return True
def get_algorithm(self):
'Acquisition d'algorithme de tri'
return self.sort.get()
def get_data_num(self):
'Obtenez le nombre de données'
return int(self.entry.get())
def draw_data(self, data):
'Dessinez une séquence de données sous forme de ligne'
#Supprimer les données une fois dessinées
for obj in self.drawn_obj:
self.canvas.delete(obj)
#Vider la liste de données dessinée car elle a été supprimée
self.drawn_obj = []
#Dessinez les nombres de la liste sous forme de rectangle
i = 0
for value in data:
#Déterminez les points de départ et d'arrivée du rectangle
#Déterminez les coordonnées horizontales du rectangle à partir de la position des données
x1 = int(self.offset_x + i * self.line_width)
x2 = int(self.offset_x + (i + 1) * self.line_width)
#Déterminez les coordonnées verticales du rectangle à partir des valeurs de données
y1 = int(self.offset_y + self.line_height * (self.num - value))
y2 = int(self.offset_y + self.line_height * self.num)
#Ajoutez une balise pour pouvoir l'effacer plus tard
tag = "line" + str(i)
self.drawn_obj.append(tag)
#Dessinez un rectangle
self.canvas.create_rectangle(
x1, y1,
x2, y2,
tag=tag,
fill="#FFA588",
width=1
)
i += 1
#Refléter immédiatement le dessin
self.canvas.update()
#Dormez pendant WAIT secondes
time.sleep(WAIT)
def update_message(self, text):
'Mettre à jour le message à afficher sur l'étiquette'
#Définir la chaîne de caractères à dessiner sur l'étiquette
self.text.set(text)
#Refléter immédiatement le dessin
self.label.update()
class Controller():
def __init__(self, view, sort):
'Créer des objets pour contrôler le tri et l'affichage'
#Afficher et trier les paramètres des objets à contrôler
self.view = view
self.sort = sort
#Accepte les événements lorsque le bouton est cliqué
self.view.button["command"] = self.button_click
def button_click(self):
'Traitement lorsqu'un clic est effectué sur un bouton'
num = self.view.get_data_num()
#Vue de départ
if not self.view.start(num):
#Mise à jour du message
self.view.update_message(
"Trop de données"
)
#Ne faites rien si vous échouez
return
#Générer une liste aléatoire du nombre de données NUM avec NUM comme valeur maximale
data = []
for _ in range(num):
import random
data.append(int(random.randint(0, num - 1)))
#Lors de la commande des données initiales par ordre décroissant
#data = []
# for i in range(num):
# data.append(num - i)
#Mise à jour du message
self.view.update_message("Tri")
#Commencer le tri
compare_num = self.sort.start(data, self.view.get_algorithm())
#Mise à jour du message
self.view.update_message(
"Le tri est terminé! (Comparaison:" + str(compare_num) + "）"
)
#Génération d'applications
app = tkinter.Tk()
app.title("Trier")
#Afficher la création d'objets
view = View(app)
#Créer un objet de tri
sort = Sort(view)
#Création d'objet contrôleur
controller = Controller(view, sort)
#En attente de réception de l'événement dans mainloop
app.mainloop()
Résumé
Il existe différents algorithmes de tri. J'espère que vous pourrez bien l'utiliser.
- Informations de référence
J'ai résumé l'algorithme de tri
Recommended Posts