Requisitos previos: interfaz gráfica de usuario de Python – tkinter
En este artículo, crearemos una aplicación GUI que nos ayudará a visualizar el algoritmo de clasificación por fusión usando Tkinter en Python.
Merge Sort es un algoritmo de clasificación popular. Tiene una complejidad de tiempo de N(logN) que es más rápido que otros algoritmos de clasificación como una burbuja o una clasificación por selección. Al crear esta aplicación, podremos visualizar cómo funciona exactamente la ordenación por combinación. Merge sort sigue el paradigma divide y vencerás. Implica tres pasos
- Dividir: dividir el problema en un subconjunto de pequeños problemas similares
- Conquistar: resolver los subproblemas recursivamente.
- Combine: combine las soluciones de los subproblemas en uno para encontrar la respuesta original
En la ordenación por combinación, la array se divide en dos mitades casi iguales, y este proceso continúa hasta que llegamos a un punto en el que solo hay dos elementos de la array para ordenar. Luego los fusionamos de manera que la array resultante sea una array ordenada. Nos ayuda a comprender o visualizar cómo mergesort utiliza la técnica divide y vencerás.
Empezando
Primero, importe los módulos necesarios para el proyecto. Importe NumPy para generar la array y mezclarla. Importe Tkinter obviamente para crear la interfaz GUI. Por último, importa tiempo para ralentizar el proceso de clasificación, crucial para la visualización.
Acercarse
- Definida una función show(), para mostrar la array como barras. Toma tres argumentos n, datos y colores. N es la longitud de la array ‘datos’. Colores es una array de colores para todas y cada una de las barras que se dibujarán en el lienzo.
- Shuffle() es una función que se explica por sí misma, simplemente baraja la array y la muestra cada vez que se llama a la función.
- Luego viene la función de implementación real mergesort().
- La función Start() activará la función mergesort y luego comenzará el algoritmo de clasificación.
- win, se crea un objeto Tkinter.
- Luego se crean un lienzo y dos botones, se les asignan las respectivas funciones que se activarán al presionar los botones.
Códigos de colores:
Mientras se fusionan, los dos elementos seleccionados se muestran en color azul. El color rojo se usa si el elemento del primer subarreglo es mayor que el elemento del último subarreglo. Luego se mostrará en verde una vez que se intercambien los dos elementos. Cuando finalmente se ordene la array, el color final de todas las barras será púrpura.
Código:
Python3
# importing all necessary modules
from tkinter import *
from tkinter import ttk
import numpy as np
import time
def show(n: int, data: list, colours: list):
# n is length of the array data
# data is the array itself
# colours is an array of colors
canvas.delete('all')
# width variable is the width of each bar
width = 1560/(3*n-1)
# gap is the spacing between the bars
gap = width/2
for i in range(n):
# this function will display an array of "bar"
canvas.create_rectangle(7+i*width+i*gap, 0, 7 +
(i+1)*width+i*gap, data[i],
fill=colours[i])
# this function will help us to see every step
# of the sorting algorithm
# the purpose of this function is to update the screen
# in runtime
win.update_idletasks()
def shuffle():
np.random.shuffle(arr)
show(N, arr, color)
def mergesort(arr, left, right):
if left < right:
m = (left+right)//2
mergesort(arr, left, m)
mergesort(arr, m+1, right)
j = m+1
if arr[m] <= arr[m+1]:
return
while left <= m and j <= right:
show(N, arr, ['blue' if x == left or x ==
j else 'grey' for x in range(N)])
time.sleep(1/speed)
if arr[left] <= arr[j]:
left += 1
else:
show(N, arr, ['red' if x == left or x ==
j else 'grey' for x in range(N)])
# array of colours where only the focused bars
# are displayed red since left >arr[j]
time.sleep(1/speed)
temp = arr[j]
# storing the smaller element in temp variable
i = j
while i != left:
arr[i] = arr[i-1]
show(N, arr, ['red' if x == i or x ==
j else 'grey' for x in range(N)])
time.sleep(1/speed)
i -= 1
# this while loop will shift all the elements one step
# to right to make the place empty for the temp variable
# upon reaching the desired location i.e. left, the
# temp value will be inserted into that location.
# this process is much like insertion sort
arr[left] = temp
show(N, arr, ['green' if x == left or x ==
j else 'grey' for x in range(N)])
time.sleep(1/speed)
left += 1
m += 1
j += 1
# this function call the mergesort function which will
# start the animation.
def start():
mergesort(arr, 0, N-1)
show(N, arr, ['purple' for _ in range(N)])
win = Tk()
N = 50 # length of the array
speed = 100 # how fast the array will be sorted
# creating the array using linspace function
# from numpy
arr = np.linspace(10, 390, N, dtype=np.uint16)
color = ['grey' for _ in range(N)]
ttk.Label(win, text='Merge Sort visualizer').pack()
canvas = Canvas(win, width=800, height=400, bg='white')
canvas.pack()
ttk.Button(win, text='Start sorting', command=start).pack(
side='right', padx=5, pady=5)
ttk.Button(win, text='Shuffle array', command=shuffle).pack(side='right')
shuffle()
show(N, arr, color)
win.mainloop()
Salida :
Publicación traducida automáticamente
Artículo escrito por rajarshiban13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA