我正在 python tkinter 中制作一个应用程序来可视化算法。我想对
window.after()partition()quick_sortwindow.after()quick_sort算法文件：
"""Module to implement algorithms"""
def bubble_sort(data, draw_data):
"""Bubble sort algorithm"""
size = len(data)
for i in range(size):
for j in range(0, size - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
draw_data(data, ['Green' if x == j + 1 else 'Red' for x in range(len(data))])
yield
draw_data(data, ['Green' for _ in range(len(data))])
def partition(data, draw_data, low, high):
"""Quick sort: Find partition position"""
pivot = data[high]
i = low - 1
draw_data(data, get_color_array(len(data), low, high, i, i))
for j in range(low, high):
if data[j] <= pivot:
draw_data(data, get_color_array(len(data), low, high, i, j, True))
i += 1
data[i], data[j] = data[j], data[i]
draw_data(data, get_color_array(len(data), low, high, i, j))
draw_data(data, get_color_array(len(data), low, high, i, low, True))
data[i + 1], data[high] = data[high], data[i + 1]
return i + 1
def quick_sort(data, draw_data, low, high):
"""Quick sort algorithm"""
if low < high:
pivot_index = partition(data, draw_data, low, high)
yield
yield from quick_sort(data, draw_data, low, pivot_index - 1)
yield from quick_sort(data, draw_data, pivot_index + 1, high)
# Grey - Unsorted elements
# Blue - Pivot point element
# White - Sorted half/partition
# Red - Starting pointer
# Yellow - Ending pointer
# Green - All elements are sorted
def get_color_array(data_len, low, high, border, cur_id_x, is_swapping=False):
"""Quick sort: Get color for data"""
color_array = []
for i in range(data_len):
if high <= i <= low:
color_array.append('Grey')
else:
color_array.append('White')
if i == low:
color_array[i] = 'Blue'
elif i == border:
color_array[i] = 'Red'
elif i == cur_id_x:
color_array[i] = 'Yellow'
if is_swapping:
if i == border or i == cur_id_x:
color_array[i] = 'Green'
return color_array
主文件：
"""Module for visualizing data structures and algorithms"""
import tkinter as tk
from tkinter import HORIZONTAL
import random
import algorithms
def repeater(data_array, draw_data_update, speed_ms, gen=None):
if not gen and navbar.curselection():
algorithm.config(text=navbar.get(navbar.curselection()))
match navbar.get(navbar.curselection()):
case "Bubble sort":
time_complexity.config(text="Time complexity: O(n^2)")
gen = algorithms.bubble_sort(data_array, draw_data_update)
case "Quick sort":
time_complexity.config(text="Time complexity: O(n^2)")
gen = algorithms.quick_sort(data_array, draw_data_update, 0, len(data_array) - 1)
case _:
pass
try:
next(gen)
if running_animation:
window.after(speed_ms, repeater, data_array, draw_data_update, speed_ms, gen)
return
except StopIteration:
draw_data(data_array, ['Green' for _ in range(len(data))])
def regenerate():
global data
global running_animation
if running_animation:
running_animation = False
min_value = int(min_entry.get())
max_value = int(max_entry.get())
input_value = int(input_size.get())
data = []
for _ in range(input_value):
data.append(random.randint(min_value, max_value + 1))
draw_data(data, ['Red' for _ in range(len(data))])
def draw_data(algo_data, color_list):
sort_canvas.delete("all")
canvas_height, canvas_width = 380, 500
x_width = canvas_width / (len(algo_data) + 1)
offset, spacing = 30, 10
normalized_data = [i / max(algo_data) for i in algo_data]
for i, height in enumerate(normalized_data):
x0 = i * x_width + offset + spacing
y0 = canvas_height - height * 340
x1 = ((i + 1) * x_width + offset)
y1 = canvas_height
sort_canvas.create_rectangle(x0, y0, x1, y1, fill=color_list[i])
sort_canvas.create_text(x0 + 2, y0, anchor='se', text=str(algo_data[i]))
window.update()
def start_algorithm():
global running_animation
if not running_animation and navbar.curselection():
running_animation = True
speed_ms = int(sort_speed.get() * 1000)
repeater(data, draw_data, speed_ms, generator)
start_button.config(text='Stop')
else:
running_animation = False
start_button.config(text='Start')
window = tk.Tk()
window.minsize(700, 580)
app_width, app_height = 700, 580
screen_width, screen_height = window.winfo_screenwidth(), window.winfo_screenheight()
mid_screen_x = (screen_width - app_width) // 2
mid_screen_y = (screen_height - app_height) // 2
window.title("StructViz")
window.iconbitmap("./assets/favicon.ico")
window.geometry(f'{app_width}x{app_height}+{mid_screen_x}+{mid_screen_y}')
select_alg = tk.StringVar()
data = []
generator = None
running_animation = False
window.columnconfigure(0, weight=0)
window.columnconfigure(1, weight=45)
window.rowconfigure((0, 1), weight=1)
window.rowconfigure(2, weight=45)
navbar = tk.Listbox(window, selectmode=tk.SINGLE, activestyle='none')
for item in ["Bubble sort", "Quick sort"]:
navbar.insert(tk.END, item)
navbar.grid(row=0, column=0, rowspan=3, sticky='nsew')
user_settings = (tk.Frame(window, background='bisque2')
.grid(row=0, column=1, columnspan=2, rowspan=2, sticky='news', padx=7, pady=5))
algorithm = tk.Label(user_settings, text='No algorithm selected', background='bisque2')
algorithm.grid(row=0, column=1, sticky='nw', padx=10, pady=10)
time_complexity = tk.Label(user_settings, text='Time complexity: ', background='bisque2')
time_complexity.grid(row=0, column=1, sticky='sw', padx=10, pady=10)
input_size = tk.Scale(user_settings, from_=5, to=60, label='Amount', background='bisque2',
orient=HORIZONTAL, resolution=1, cursor='arrow')
input_size.grid(row=0, column=1, sticky='n', padx=10, pady=10)
min_entry = tk.Scale(user_settings, from_=0, to=10, resolution=1, background='bisque2',
orient=HORIZONTAL, label="Minimum Value")
min_entry.grid(row=1, column=1, sticky='s', padx=10, pady=10)
max_entry = tk.Scale(user_settings, from_=10, to=100, resolution=1, background='bisque2',
orient=HORIZONTAL, label="Maximum Value")
max_entry.grid(row=1, column=1, sticky='se', padx=10, pady=10)
sort_speed = tk.Scale(user_settings, from_=0.01, to=2.0, length=100, digits=3, background='bisque2',
resolution=0.01, orient=HORIZONTAL, label="Speed")
sort_speed.grid(row=0, column=1, sticky='ne', padx=10, pady=10)
start_button = (tk.Button(user_settings, text="Start", command=start_algorithm, background='bisque2'))
start_button.grid(row=1, column=1, sticky='nw', padx=10, pady=10)
tk.Button(user_settings, text="Regenerate", command=regenerate, background='bisque2').grid(
row=1, column=1, sticky='sw', padx=10, pady=10)
sort_canvas = tk.Canvas(window, background='bisque2')
sort_canvas.grid(row=2, column=1, sticky='news', padx=5, pady=5)
window.mainloop()
尝试让排序速度恒定，但是在可视化快速排序时，程序时慢时快。
您需要对
partition()partition()...
def partition(data, draw_data, low, high):
pivot = data[high]
i = low - 1
...
for j in range(low, high):
if data[j] <= pivot:
...
i += 1
data[i], data[j] = data[j], data[i]
yield
...
data[i + 1], data[high] = data[high], data[i + 1]
...
yield i + 1
def quick_sort(data, draw_data, low, high):
if low < high:
for item in partition(data, draw_data, low, high):
if item is not None:
pivot_index = item
yield
yield from quick_sort(data, draw_data, low, pivot_index - 1)
yield from quick_sort(data, draw_data, pivot_index + 1, high)
...