Hình dung thuật toán sắp xếp: Sắp xếp chèn

Thuật toán sắp xếp chèn có thể dễ dàng được hiểu bằng cách trực quan hóa. Trong bài viết này, một chương trình trực quan hóa thuật toán sắp xếp chèn đã được triển khai. 
Giao diện người dùng đồ họa (GUI) được triển khai bằng Python sử dụng thư viện PyGame . 
Cách 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).

• 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.

Nhận xét: Chúng ta có thể thấy rõ ràng từ hình ảnh minh họa của Insertion Sort rằng Insertion Sort chậm hơn nhiều so với các thuật toán sắp xếp khác như Mergesort hoặc Quicksort.  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:

Khởi tạo: 

Sắp xếp: 
 

Cuối cùng: 
 

Vui lòng đả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à bản triển khai của trình trực quan hóa ở trên:

# Cài đặt bằng Python cho 
# Bộ hiển thị sắp xếp: Insertion Sort 

# Thư viện cần thiết
import pygame
import random
import time
pygame.font.init()
startTime = time.time()
# Cửa sổ tổng thể
screen = pygame.display.set_mode(
                        (900, 650)
                    )

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

# Bỏ ghi chú các dòng dưới nếu muốn đặt 
# biểu tượng cho trình hiển thị
# 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
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 để làm mới 
# các cập nhật 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: Insertion Sort
def insertionSort(array):

    for i in range(1, len(array)):
        pygame.event.pump() 
        refill()
        key = array[i]
        arr_clr[i]= clr[2]
        j = i-1
        while j>= 0 and key<array[j]:
            arr_clr[j]= clr[2]
            array[j + 1]= array[j]
            refill()
            arr_clr[j]= clr[3]
            j = j-1
        array[j + 1]= key 
        refill()
        arr_clr[i]= clr[0]

# Hàm để vẽ các giá trị của mảng
def draw():
    # Văn bản được render
    txt = fnt.render("SORT: PRESS 'ENTER'", \
                                1, (0, 0, 0))
    # Vị trí đặt 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:"\
           "INSERTION 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 dò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 được chạy 
# liên tục để giữ cửa sổ hiển thị
while run:
    # nền
    screen.fill((255, 255, 255))

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

        # Nếu bấm 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:
                insertionSort(array)     
    draw()
    pygame.display.update()
    
pygame.quit()