Un algoritmo como Heap sort puede entenderse fácilmente mediante la visualización. En este artículo, se ha implementado un programa que visualiza el algoritmo Heap Sort.
La interfaz gráfica de usuario (GUI) se implementa en Python utilizando la biblioteca pygame .
Acercarse:
Genere una array aleatoria y llene la ventana de pygame con barras. Las barras son líneas verticales rectas, que representan elementos de array.
- Establezca todas las barras en color verde (sin clasificar).
- Apile la array para realizar la clasificación.
- Después de Heapify, las barras grandes están al principio seguidas de barras más pequeñas.
- Use pygame.time.delay() para ralentizar el algoritmo, de modo que podamos ver el proceso de clasificación.
- Implemente un temporizador para ver cómo funciona el algoritmo.
- Las acciones se realizan utilizando el método ‘pygame.event.get()’, que almacena todos los eventos que realiza el usuario, como inicio, reinicio.
- El color azul se utiliza para resaltar las barras que participan en la clasificación en un momento determinado.
- El color naranja resalta las barras ordenadas.
Observaciones:
Podemos ver claramente en la visualización Heap Sort, que Heap Sort es muy rápido en comparación con otros algoritmos de clasificación, como la clasificación por inserción o la clasificación por selección, y una velocidad similar a la clasificación por combinación .
Ejemplos:
Aporte:
Presione la tecla «Enter» para realizar la visualización.
Presione la tecla «R» para generar una nueva array.
Producción:
Inicial:
Después de la acumulación de array:
Clasificación:
Final:
Asegúrese de instalar la biblioteca pygame antes de ejecutar el siguiente programa.
A continuación se muestra la implementación del visualizador anterior:
Python3
# Python implementation of the
# Sorting visualiser: Heap Sort
# Imports
import pygame
import random
import time
pygame.font.init()
startTime = time.time()
# Total window
screen = pygame.display.set_mode(
(900, 650)
)
# Title and Icon
pygame.display.set_caption(
"SORTING VISUALISER"
)
# Uncomment below lines for setting
# up the icon for the visuliser
# img = pygame.image.load('sorticon.png')
# pygame.display.set_icon(img)
# Boolean variable to run
# the program in while loop
run = True
# Window size and some initials
width = 900
length = 600
array = [0]*151
arr_clr = [(0, 204, 102)]*151
clr_ind = 0
clr = [(0, 204, 102), (255, 0, 0),
(0, 0, 153), (255, 102, 0)]
fnt = pygame.font.SysFont("comicsans", 30)
fnt1 = pygame.font.SysFont("comicsans", 20)
# Function to generate new Array
def generate_arr():
for i in range(1, 151):
arr_clr[i] = clr[0]
array[i] = random.randrange(1, 100)
# Initially generate a array
generate_arr()
# Function to refill the
# updates on the window
def refill():
screen.fill((255, 255, 255))
draw()
pygame.display.update()
pygame.time.delay(10)
# Sorting Algorithm: Heap Sort
def heapSort(array):
n = len(array)
for i in range(n//2-1, -1, -1):
pygame.event.pump()
heapify(array, i, n)
for i in range(n-1, 0, -1):
array[i], array[0] = array[0], array[i]
arr_clr[i] = clr[1]
refill()
heapify(array, 0, i)
def heapify(array, root, size):
left = root * 2 + 1
right = root * 2 + 2
largest = root
if left < size and array[left] > array[largest]:
largest = left
if right < size and array[right] > array[largest]:
largest = right
if largest != root:
arr_clr[largest] = clr[2]
arr_clr[root] = clr[2]
array[largest],\
array[root] = array[root],\
array[largest]
refill()
arr_clr[largest] = clr[0]
arr_clr[root] = clr[0]
heapify(array, largest, size)
refill()
# Function to Draw the array values
def draw():
# Text should be rendered
txt = fnt.render("SORT: PRESS 'ENTER'",
1, (0, 0, 0))
# Position where text is placed
screen.blit(txt, (20, 20))
txt1 = fnt.render("NEW ARRAY: PRESS 'R'",
1, (0, 0, 0))
screen.blit(txt1, (20, 40))
txt2 = fnt1.render("ALGORITHM USED:" +
"HEAP SORT", 1, (0, 0, 0))
screen.blit(txt2, (600, 60))
text3 = fnt1.render("Running Time(sec): " +
str(int(time.time() - startTime)),
1, (0, 0, 0))
screen.blit(text3, (600, 20))
element_width = (width-150)//150
boundry_arr = 900 / 150
boundry_grp = 550 / 100
pygame.draw.line(screen, (0, 0, 0), (0, 95),
(900, 95), 6)
# Drawing the array values as lines
for i in range(1, 151):
pygame.draw.line(screen, arr_clr[i],
(boundry_arr * i-3, 100),
(boundry_arr * i-3,
array[i]*boundry_grp + 100),\
element_width)
# Program should be run
# continuously to keep the window open
while run:
# background
screen.fill((255, 255, 255))
# Event handler stores all event
for event in pygame.event.get():
# If we click Close button in window
if event.type == pygame.QUIT:
run = False
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_r:
generate_arr()
if event.key == pygame.K_RETURN:
heapSort(array)
draw()
pygame.display.update()
pygame.quit()