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

Thuật toán như Tìm kiếm Tam 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 Tam 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 đỏ làm nổi bật thanh bên trái và bên phải.

• Màu cam làm nổi bật thanh mid1 và mid2.

Dưới đây là cách triển khai công cụ trực quan hóa ở trên.

# Cài đặt Python cho
# Trình trực quan hóa thuật toán tìm kiếm tam phâ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(
    "TERNARY SEARCH VISUALISER"
)

# Bỏ comment các dòng dưới nếu bạn muốn
# đặt 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ố giá trị 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)


# Tạo mảng lần đầu tiên
generate_arr()

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


def ternarySearch(array, key):
    left = 1
    right = len(array)-1

    while left <= right:
        pygame.event.pump()
        arr_clr[left] = clr[1]
        arr_clr[right] = clr[1]
        mid1 = left+(right-left)//3
        mid2 = right-(right-left)//3
        arr_clr[mid1] = clr[3]
        arr_clr[mid2] = clr[3]
        refill()
        pygame.event.pump()
        refill()
        refill()
        arr_clr[left] = clr[0]
        arr_clr[right] = clr[0]
        arr_clr[mid1] = clr[0]
        arr_clr[mid2] = clr[0]
        
        if key == array[mid1]:
            arr_clr[mid1] = clr[2]
            return 1
        
        if key == array[mid2]:
            arr_clr[mid1] = clr[2]
            return 1

        if key < array[mid1]:
            right = mid1-1
        elif key > array[mid2]:
            left = mid2+1
        else:
            left = mid1+1
            right = mid2-1
        refill()

    return -1
  
# Hàm vẽ các giá trị của mảng
def draw():
  
    # Hiển thị văn bản
    txt = fnt.render("SEARCH: PRESS 'ENTER'",
                     1, (0, 0, 0))
    
    # Vị trí hiển thị văn bản
    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)

    # Vẽ các giá trị của mảng dưới dạng đường thẳng
    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))


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

    # Bộ xử lý sự kiện lưu trữ tất cả sự kiện
    for event in pygame.event.get():

        # Nếu chúng ta 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 = ternarySearch(array, key)
                print("hello")

            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: