Hình dung tìm kiếm nhị phân bằng Pygame trong Python

Thuật toán như Tìm kiếm Nhị phân có thể được hiểu dễ dàng bằng cách trực quan hóa. Bài viết này trình bày một chương trình trực quan hóa Thuật toán Tìm kiếm Nhị phân. Giao diện Người dùng Đồ họa (GUI) được triển khai bằng Python sử dụng thư viện pygame .

Tiếp cận

Tạo mảng ngẫu nhiên, sắp xếp nó bằng bất kỳ thuật toán sắp xếp nào và điền các thanh vào cửa sổ PyGame. Thanh là các đường thẳng đứng, biểu diễn các phần tử của mảng.

• Đặt tất cả các thanh thành màu xanh lá cây.

• Sử dụng pygame.time.delay() để làm chậm thuật toán, để chúng ta có thể thấy được quá trình tìm kiếm.

• Triển khai bộ đếm thời gian để xem thuật toán hoạt động như thế nào.

• Các hành động được thực hiện bằng phương thức 'pygame.event.get()', phương thức này lưu trữ tất cả các sự kiện mà người dùng thực hiện, chẳng hạn như bắt đầu, đặt lại.

• Màu xanh được sử dụng để làm nổi bật thanh bằng với khóa nếu tìm thấy.

• Màu cam làm nổi bật thanh bên trái và bên phải.

Dưới đây là cách triển khai trình trực quan hóa ở trên:

# Triển khai bằng Python cho chương trình 
# trực quan hóa thuật toán sắp xếp: Sắp xếp chèn

# Thư viện
import pygame
import random
import time

pygame.font.init()
startTime = time.time()

# Cửa sổ chính
screen = pygame.display.set_mode(
    (900, 650)
)

# Tiêu đề và biểu tượng
pygame.display.set_caption(
    "BINARY SEARCH VISUALISER"
)

# Bỏ ghi chú các dòng bên dưới nếu muốn
# thiết lập biểu tượng cho trình trực quan
# img = pygame.image.load('sorticon.png')
# pygame.display.set_icon(img)

# Biến boolean để chạy chương trình
# trong vòng lặp while
run = True

# Kích thước cửa sổ và một số khởi tạo
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)

# Thuật toán sắp xếp: 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)

# Hàm tạo mảng mới
def generate_arr():
    for i in range(1, 151):
        arr_clr[i] = clr[0]
        array[i] = random.randrange(1, 100)
    heapSort(array)

# Khởi tạo mảng ban đầu
generate_arr()

# Hàm để cập nhật lại cửa sổ hiển thị
def refill():
    screen.fill((255, 255, 255))
    draw()
    pygame.display.update()
    pygame.time.delay(200)

# Thuật toán tìm kiếm nhị phân
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

# Hàm vẽ giá trị mảng
def draw():
    
    # Hiển thị văn bản
    txt = fnt.render("TÌM KIẾM: NHẤN 'ENTER'",
                     1, (0, 0, 0))
    
    # Vị trí hiển thị văn bản
    screen.blit(txt, (20, 20))
    txt1 = fnt.render("MẢNG MỚI: NHẤN 'R'",
                      1, (0, 0, 0))
    screen.blit(txt1, (20, 40))
    txt2 = fnt1.render("NHẬP SỐ CẦN TÌM:" +
                       str(key), 1, (0, 0, 0))
    screen.blit(txt2, (600, 60))
    text3 = fnt1.render("Thời gian chạy (giây): " +
                        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)

    # Vẽ các giá trị của mảng dưới dạng các đường kẻ
    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("Tìm thấy. Nhấn N để đặt lại", 1, (0, 0, 0))
        screen.blit(text4, (100, 300))
    
    elif foundkey == -1:
        text4 = bigfont.render(
            "Không tìm thấy. Nhấn N để đặt lại", 1, (0, 0, 0))
        screen.blit(text4, (30, 300))

# Chương trình cần chạy liên tục
# để giữ cửa sổ luôn hiển thị
while run:
    
    # Nền
    screen.fill((255, 255, 255))

    # Xử lý sự kiện, lưu tất cả các sự kiện
    for event in pygame.event.get():

        # Nếu nhấn nút đóng cửa sổ
        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()

Đầu ra: