Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
273 views
in Technique[技术] by (71.8m points)

python - Sort Algorithm Visualization: How to pull values to animate the canvas, from inside a tight loop

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

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

1.4m articles

1.4m replys

5 comments

57.0k users

...