Hình dung thuật toán sắp xếp: Sắp xếp đống

Thuật toán sắp xếp Heap 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 sắp xếp Heap.

Giao diện người dùng đồ họa (GUI) được triển khai bằng Python bằng thư viện pygame .

Tiếp cận:

Tạo mảng ngẫu nhiên 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 (chưa sắp xếp).

• Xếp chồng mảng để thực hiện sắp xếp.

• Sau Heapify, các thanh lớn sẽ ở đầu, tiếp theo là các thanh nhỏ hơn.

• 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 sắp xếp.

• 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 các thanh liên quan đến việc sắp xếp tại một thời điểm cụ thể.

• Màu cam làm nổi bật các thanh đã sắp xếp.

Quan sát:

Chúng ta có thể thấy rõ từ hình ảnh minh họa của Heap Sort rằng Heap Sort nhanh hơn nhiều so với các thuật toán sắp xếp khác như Insertion Sort hay Selection Sort và có tốc độ tương đương với Merge Sort .

Ví dụ:

Đầu vào:

Nhấn phím “Enter” để thực hiện trực quan hóa.

Nhấn phím “R” để tạo mảng mới.

Đầu ra:

Ban đầu:

Sau khi xếp chồng mảng:

Sắp xếp:

Cuối cùng:

Hãy đảm bảo cài đặt thư viện pygame trước khi chạy chương trình bên dưới.

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

# Cài đặt Python cho
# Trình trực quan hóa thuật toán sắp xếp: Heap Sort

# 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(
    "SORTING VISUALISER"
)

# Bỏ comment các dòng dưới để
# 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ố giá trị khởi tạo
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)

# 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)


# Tạo mảng ban đầu
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(10)


# 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):
        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()

# Hàm vẽ các giá trị của mảng
def draw():

    # Văn bản cần hiển thị
    txt = fnt.render("SORT: 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("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)

    # 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)


# Chương trình cần chạy liên tục
# để giữ cửa sổ luôn 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 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:
                generate_arr()
            if event.key == pygame.K_RETURN:
                heapSort(array)
    draw()
    pygame.display.update()

pygame.quit()