Visualización de búsqueda binaria usando Pygame en Python

Un algoritmo como la búsqueda binaria se puede entender fácilmente mediante la visualización. En este artículo se ha implementado un programa que visualiza el Algoritmo de Búsqueda Binaria. La interfaz gráfica de usuario (GUI) se implementa en Python utilizando la biblioteca pygame .

Acercarse

Genere una array aleatoria, clasifíquela usando cualquier algoritmo de clasificación y llene la ventana de pygame con barras. Las barras son líneas rectas verticales que representan elementos de array.

  • Establezca todas las barras en color verde.
  • Use pygame.time.delay() para ralentizar el algoritmo, de modo que podamos ver el proceso de búsqueda.
  • 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 usa para resaltar la barra igual a la clave si se encuentra.
  • El color naranja resalta las barras izquierda y derecha.

A continuación se muestra la implementación del visualizador anterior:

Python

# Python implementation of the
# Sorting visualiser: Insertion 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(
    "BINARY SEARCH 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
key = 0
foundkey = False
  
arr_clr = [(0, 204, 102)]*151
clr_ind = 0
  
clr = [(0, 204, 102), (255, 0, 0),
       (0, 0, 153), (255, 102, 0)]
  
bigfont = pygame.font.SysFont("comicsans", 70)
fnt = pygame.font.SysFont("comicsans", 30)
fnt1 = pygame.font.SysFont("comicsans", 20)
  
# Sorting Algorithm: Heap Sort
def heapSort(array):
    n = len(array)
      
    for i in range(n//2-1, -1, -1):
        heapify(array, i, n)
      
    for i in range(n-1, 0, -1):
        array[i], array[0] = array[0], array[i]
        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:
        array[largest], array[root] = array[root], array[largest]
        heapify(array, largest, size)
  
# 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)
    heapSort(array)
  
  
# 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(200)
  
  
def binarySearch(array, key):
    left = 0
    right = len(array)-1
      
    while left < right:
        arr_clr[left] = clr[1]
        arr_clr[right] = clr[1]
        refill()
        refill()
        mid = left+(right-left)//2
          
        if array[mid] == key:
            arr_clr[left] = clr[0]
            arr_clr[right] = clr[0]
            arr_clr[mid] = clr[2]
            return 1
          
        elif array[mid] < key:
            arr_clr[left] = clr[0]
            left = mid+1
          
        else:
            arr_clr[right] = clr[0]
            right = mid-1
        refill()
    arr_clr[left] = clr[0]
    arr_clr[right] = clr[0]
    refill()
    return -1
  
  
# Function to Draw the array values
def draw():
      
    # Text should be rendered
    txt = fnt.render("SEARCH: 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("ENTER NUMBER TO SEARCH:" +
                       str(key), 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)
    if foundkey == 1:
        text4 = bigfont.render("Key Found. Press N to Reset Key", 1, (0, 0, 0))
        screen.blit(text4, (100, 300))
      
    elif foundkey == -1:
        text4 = bigfont.render(
            "Key Not Found. Press N to Reset Key", 1, (0, 0, 0))
        screen.blit(text4, (30, 300))
  
  
# 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:
                key = 0
                foundkey = 0
                generate_arr()
            if event.key == pygame.K_n:
                foundkey = 0
                key = 0
                for i in range(0, len(array)):
                    arr_clr[i] = clr[0]
            if event.key == pygame.K_RETURN and key != 0:
                foundkey = binarySearch(array, key)
            if event.key == pygame.K_0:
                key = key*10
            if event.key == pygame.K_1:
                key = key*10+1
            if event.key == pygame.K_2:
                key = key*10+2
            if event.key == pygame.K_3:
                key = key*10+3
            if event.key == pygame.K_4:
                key = key*10+4
            if event.key == pygame.K_5:
                key = key*10+5
            if event.key == pygame.K_6:
                key = key*10+6
            if event.key == pygame.K_7:
                key = key*10+7
            if event.key == pygame.K_8:
                key = key*10+8
            if event.key == pygame.K_9:
                key = key*10+9
    draw()
    pygame.display.update()
  
pygame.quit()

Producción:

Publicación traducida automáticamente

Artículo escrito por manoj_n y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *