排序算法可视化:如何从紧密循环中提取值以动画画布 [英] Sort Algorithm Visualization: How to pull values to animate the canvas, from inside a tight loop

问题描述

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

I am working on a visualization of different sorting algorithms using the height of different bars with tkinter. I have been able to shuffle the bars and also sort them after some help. The problem I am having now is slowing the sorting of the bars down so it can be seen how each algorithm works. Here is what I have so far:

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() 方法，但它所做的只是冻结窗口并使其不响应.没有那个方法，它工作得很好，只是没有以可见的速度前进.

As you can see I tried using the after() method in the insertion sort function, but all it does is freeze the window and make it not respond. Without that method, it works fine, just doesn't go at a pace that can be seen.

推荐答案

利用一个生成器函数(关键字yield)，你可以暂停代码mid loop的执行来花时间显示发生变化的画布元素，更新计算等，然后在生成器上重复调用next继续执行，直到排序完成.

Making use of a generator function (keyword yield), you can suspend the execution of the code mid loop to take the time to display the canvas elements that have changed, update calculations, etc., then resume the execution upon calling next on the generator repeatedly, until completion of the sort.

我在代码中添加了一些注释，但最好的方法可能是盯着它看，直到你说服自己它按预期工作.这是一个你需要理解的模式，因为它对构建你想要的那种动画非常有用构建.

I put some comments in the code, but the best way, is probably to stare at it until you convince yourself that it works as it is supposed to. This is a pattern that you need to understand, as it is very useful to construct the sort of animations you want to 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()

这篇关于排序算法可视化:如何从紧密循环中提取值以动画画布的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！