Skip to main content
 首页 » 编程设计

python之从紧密循环内部排序算法可视化 : How to pull values to animate the canvas,

2024年11月24日8haluo1

我正在使用 tkinter 使用不同条形的高度来可视化不同的排序算法。我已经能够洗牌,并在一些帮助后对它们进行排序。我现在遇到的问题是减慢条形的排序速度,以便可以看到每种算法的工作原理。 这是我目前所拥有的:

import tkinter as tk 
import random 
 
def swap_two_pos(pos_0, pos_1): 
    Bar1x1, _, Bar1x2, _ = canvas.coords(pos_0) 
    Bar2x1, _, Bar2x2, _ = canvas.coords(pos_1) 
    canvas.move(pos_0, Bar2x1-Bar1x1, 0) 
    canvas.move(pos_1, Bar1x2-Bar2x2, 0) 
 
 
def insertion_sort(): 
    global barList 
    global lengthList 
 
    for i in range(len(lengthList)): 
        cursor = lengthList[i] 
        cursorBar = barList[i] 
        pos = i 
 
        while pos > 0 and lengthList[pos - 1] > cursor: 
            lengthList[pos] = lengthList[pos - 1] 
            barList[pos], barList[pos - 1] = barList[pos - 1], barList[pos] 
            canvas.after(1000,swap_two_pos(barList[pos],barList[pos-1])) 
            pos -= 1 
 
        lengthList[pos] = cursor 
        barList[pos] = cursorBar 
        swap_two_pos(barList[pos],cursorBar) 
 
def shuffle(): 
    global barList 
    global lengthList 
    canvas.delete('all') 
    xstart = 5 
    xend = 15 
    barList = [] 
    lengthList = [] 
 
    for x in range(1,60): 
        randomY = random.randint(1,390) 
        x = canvas.create_rectangle(xstart,randomY,xend,395, fill='red') 
        barList.append(x) 
        xstart += 10 
        xend += 10 
 
    for bar in barList: 
        x = canvas.coords(bar) 
        length = x[3]-x[1] 
        lengthList.append(length) 
 
    for i in range(len(lengthList)-1): 
        if lengthList[i] == min(lengthList): 
            canvas.itemconfig(barList[i], fill='blue') 
        elif lengthList[i] == max(lengthList): 
            canvas.itemconfig(barList[i], fill='green') 
 
window = tk.Tk() 
window.title('Sorting') 
window.geometry('600x435') 
canvas = tk.Canvas(window, width='600', height='400') 
canvas.grid(column=0,row=0, columnspan = 50) 
 
insert = tk.Button(window, text='Insertion Sort', command=insertion_sort) 
shuf = tk.Button(window, text='Shuffle', command=shuffle) 
insert.grid(column=1,row=1) 
shuf.grid(column=0, row=1) 
 
shuffle() 
window.mainloop() 

如您所见,我尝试在插入排序函数中使用 after() 方法,但它所做的只是卡住窗口并使其不响应。没有这种方法,它工作正常,只是没有以可见的速度进行。

请您参考如下方法:

利用生成器函数(关键字yield),你可以在循环中暂停代码的执行,以花时间显示已更改的 Canvas 元素、更新计算等,然后在生成器上重复调用 next 继续执行,直到完成排序。

我在代码中添加了一些注释,但最好的方法可能是盯着它看,直到您确信它可以正常工作。这是您需要了解的模式,因为它对于构建您想要的那种动画非常有用 build 。

import tkinter as tk 
import random 
 
 
def swap_two_pos(pos_0, pos_1): 
    Bar1x1, _, Bar1x2, _ = canvas.coords(pos_0) 
    Bar2x1, _, Bar2x2, _ = canvas.coords(pos_1) 
    canvas.move(pos_0, Bar2x1-Bar1x1, 0) 
    canvas.move(pos_1, Bar1x2-Bar2x2, 0) 
 
 
def _insertion_sort(): 
    global barList 
    global lengthList 
 
    for i in range(len(lengthList)): 
        cursor = lengthList[i] 
        cursorBar = barList[i] 
        pos = i 
 
        while pos > 0 and lengthList[pos - 1] > cursor: 
            lengthList[pos] = lengthList[pos - 1] 
            barList[pos], barList[pos - 1] = barList[pos - 1], barList[pos] 
            swap_two_pos(barList[pos],barList[pos-1])   # <-- updates the display 
            yield                                       # <-- suspends the execution 
            pos -= 1                                    # <-- execution resumes here when next is called 
 
        lengthList[pos] = cursor 
        barList[pos] = cursorBar 
        swap_two_pos(barList[pos],cursorBar) 
 
 
worker = None    # <-- Not a thread in spite of the name. 
 
def insertion_sort():     # <-- commands the start of both the animation, and the sort 
    global worker 
    worker = _insertion_sort() 
    animate() 
 
 
def animate():      # <-- commands resuming the sort once the display has been updated 
                    # controls the pace of the animation 
    global worker 
    if worker is not None: 
        try: 
            next(worker) 
            window.after(10, animate)    # <-- repeats until the sort is complete, 
        except StopIteration:            # when the generator is exhausted 
            worker = None 
        finally: 
            window.after_cancel(animate) # <-- stop the callbacks 
 
 
def shuffle(): 
    global barList 
    global lengthList 
    canvas.delete('all') 
    xstart = 5 
    xend = 15 
    barList = [] 
    lengthList = [] 
 
    for x in range(1, 60): 
        randomY = random.randint(1, 390) 
        x = canvas.create_rectangle(xstart, randomY, xend, 395, fill='red') 
        barList.append(x) 
        xstart += 10 
        xend += 10 
 
    for bar in barList: 
        x = canvas.coords(bar) 
        length = x[3] - x[1] 
        lengthList.append(length) 
 
    for i in range(len(lengthList)-1): 
        if lengthList[i] == min(lengthList): 
            canvas.itemconfig(barList[i], fill='blue') 
        elif lengthList[i] == max(lengthList): 
            canvas.itemconfig(barList[i], fill='green') 
 
 
window = tk.Tk() 
window.title('Sorting') 
window.geometry('600x435') 
canvas = tk.Canvas(window, width='600', height='400') 
canvas.grid(column=0,row=0, columnspan = 50) 
 
insert = tk.Button(window, text='Insertion Sort', command=insertion_sort) 
shuf = tk.Button(window, text='Shuffle', command=shuffle) 
insert.grid(column=1,row=1) 
shuf.grid(column=0, row=1) 
 
shuffle() 
window.mainloop()