如何在 python tkinter 中正确实施冒泡排序算法？
How do I correctly implement a bubble sort algorithm in python tkinter?
我正在撰写有关排序算法的系列文章，第一部分是关于冒泡排序的，我已经准备好 GUI 元素，但排序算法本身无法正常工作。它随机交换一系列不同长度的行，但排序没有按预期进行。它是用 python Tkinter 编写的，我认为主要问题来自我如何将排序编程为两个列表，一个在屏幕上，一个在内存中。如果您也能向我解释一下我的错误，那将很有帮助。
import tkinter as tk
import random
def swap_two_pos(pos_0, pos_1):
"""This does the graphical swapping of the rectangles on the canvas
by moving one rectangle to the location of the other, and vice versa
"""
x_00, _, x_01, _ = canvas.coords(pos_0)
x_10, _, x_11, _ = canvas.coords(pos_1)
# moves each rectangle to the x position of the other; y remains unchanged
canvas.move(pos_0, x_10-x_00, 0)
canvas.move(pos_1, x_01-x_11, 0)
def sort_two(pos_0, pos_1):
x_00, y1, x_01, _ = canvas.coords(pos_0)
x_10, y2, x_11, _ = canvas.coords(pos_1)
# moves each rectangle to the x position of the other; y remains unchanged
if y2 > y1:
canvas.move(pos_0, x_10-x_00, 0)
canvas.move(pos_1, x_01-x_11, 0)
def rand_sort():
for i in range(50000):
rd1 = random.randint(0, 58)
rd2 = random.randint(0, 58)
pos_1 = barList[rd1]
pos_2 = barList[rd2]
sort_two(pos_1, pos_2)
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
def sort ():
n = len(barList)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
sort_two(barList[j], barList[j+1])
barList[j], barList[j+1] = barList[j+1], barList[j]
else:
break
def random_swap():
"""Not a sort yet, but you have the bare bones operations
so the swap is executed
"""
for i in range(500):
rd1 = random.randint(0, 58)
rd2 = random.randint(0, 58)
pos_0 = barList[rd1]
pos_1 = barList[rd2]
swap_two_pos(pos_0, pos_1)
# it is necessary to swap the values in the list too
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
window = tk.Tk()
window.title('Sorting')
window.geometry('600x400')
# button to command the swap
tk.Button(window, text='swap', command=random_swap).pack()
tk.Button(window, text='sort', command=sort).pack()
xstart = 5
xend = 15
canvas = tk.Canvas(window, width='900', height='900')
canvas.pack()
barList = []
lengthList = []
Y = 5
for x in range(1,60):
bar = canvas.create_rectangle(xstart, Y, xend, 395, fill='red')
barList.append(bar)
xstart += 10
xend += 10
Y += 5
for bar in barList:
x = canvas.coords(bar)
length = x[3]-x[1]
lengthList.append(length)
window.mainloop()
最大的问题是 sort_two 里面有 if
if y2 > y1:
canvas.move(pos_0, x_10-x_00, 0)
canvas.move(pos_1, x_01-x_11, 0)
仅当 y2 > y1
时才替换元素
但在 sort_two() 之后你使用 barList
sort_two(pos_1, pos_2)
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
始终替换列表中的元素。
这样你在屏幕上的结果是错误的。
您可以从 sort_two() return True/False 来控制何时更改 barList
上的元素
if y2 > y1:
canvas.move(pos_0, x_10-x_00, 0)
canvas.move(pos_1, x_01-x_11, 0)
return True
else:
return False
和
if sort_two(pos_1, pos_2):
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
这里是最终代码
我使用简单的计算来替换 canvas
上的元素
x1, _, _, _ = canvas.coords(pos_0)
x2, _, _, _ = canvas.coords(pos_1)
diff = x1 - x2
canvas.move(pos_0, -diff, 0)
canvas.move(pos_1, +diff, 0)
我也删除了
else:
break
每次替换后停止动画，它需要一次又一次地单击按钮 sort - 我使用
window.update()
time.sleep(0.1)
因此它会（缓慢地）显示动画直到排序结束，我不必单击按钮 sort
import tkinter as tk
import random
import time
def swap_two_pos(pos_0, pos_1):
"""This does the graphical swapping of the rectangles on the canvas
by moving one rectangle to the location of the other, and vice versa
"""
x1, _, _, _ = canvas.coords(pos_0)
x2, _, _, _ = canvas.coords(pos_1)
diff = x1 - x2
canvas.move(pos_0, -diff, 0)
canvas.move(pos_1, +diff, 0)
def sort_two(pos_0, pos_1):
x1, y1, _, _ = canvas.coords(pos_0)
x2, y2, _, _ = canvas.coords(pos_1)
diff = x1 - x2
# moves each rectangle to the x position of the other; y remains unchanged
if y2 > y1:
canvas.move(pos_0, -diff, 0)
canvas.move(pos_1, +diff, 0)
return True
else:
return False
def rand_sort():
for i in range(50000):
rd1 = random.randint(0, 58)
rd2 = random.randint(0, 58)
pos_1 = barList[rd1]
pos_2 = barList[rd2]
if sort_two(pos_1, pos_2):
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
def sort ():
n = len(barList)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
if sort_two(barList[j], barList[j+1]):
barList[j], barList[j+1] = barList[j+1], barList[j]
window.update()
time.sleep(0.1)
def random_swap():
"""Not a sort yet, but you have the bare bones operations
so the swap is executed
"""
for i in range(500):
rd1 = random.randint(0, 58)
rd2 = random.randint(0, 58)
pos_0 = barList[rd1]
pos_1 = barList[rd2]
swap_two_pos(pos_0, pos_1)
# it is necessary to swap the values in the list too
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
window = tk.Tk()
window.title('Sorting')
window.geometry('600x400')
# button to command the swap
tk.Button(window, text='swap', command=random_swap).pack()
tk.Button(window, text='sort', command=sort).pack()
xstart = 5
xend = 15
canvas = tk.Canvas(window, width='900', height='900')
canvas.pack()
barList = []
lengthList = []
Y = 5
for x in range(1,60):
bar = canvas.create_rectangle(xstart, Y, xend, 395, fill='red')
barList.append(bar)
xstart += 10
xend += 10
Y += 5
for bar in barList:
x = canvas.coords(bar)
length = x[3]-x[1]
lengthList.append(length)
window.mainloop()
我正在撰写有关排序算法的系列文章，第一部分是关于冒泡排序的，我已经准备好 GUI 元素，但排序算法本身无法正常工作。它随机交换一系列不同长度的行，但排序没有按预期进行。它是用 python Tkinter 编写的，我认为主要问题来自我如何将排序编程为两个列表，一个在屏幕上，一个在内存中。如果您也能向我解释一下我的错误，那将很有帮助。
import tkinter as tk
import random
def swap_two_pos(pos_0, pos_1):
"""This does the graphical swapping of the rectangles on the canvas
by moving one rectangle to the location of the other, and vice versa
"""
x_00, _, x_01, _ = canvas.coords(pos_0)
x_10, _, x_11, _ = canvas.coords(pos_1)
# moves each rectangle to the x position of the other; y remains unchanged
canvas.move(pos_0, x_10-x_00, 0)
canvas.move(pos_1, x_01-x_11, 0)
def sort_two(pos_0, pos_1):
x_00, y1, x_01, _ = canvas.coords(pos_0)
x_10, y2, x_11, _ = canvas.coords(pos_1)
# moves each rectangle to the x position of the other; y remains unchanged
if y2 > y1:
canvas.move(pos_0, x_10-x_00, 0)
canvas.move(pos_1, x_01-x_11, 0)
def rand_sort():
for i in range(50000):
rd1 = random.randint(0, 58)
rd2 = random.randint(0, 58)
pos_1 = barList[rd1]
pos_2 = barList[rd2]
sort_two(pos_1, pos_2)
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
def sort ():
n = len(barList)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
sort_two(barList[j], barList[j+1])
barList[j], barList[j+1] = barList[j+1], barList[j]
else:
break
def random_swap():
"""Not a sort yet, but you have the bare bones operations
so the swap is executed
"""
for i in range(500):
rd1 = random.randint(0, 58)
rd2 = random.randint(0, 58)
pos_0 = barList[rd1]
pos_1 = barList[rd2]
swap_two_pos(pos_0, pos_1)
# it is necessary to swap the values in the list too
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
window = tk.Tk()
window.title('Sorting')
window.geometry('600x400')
# button to command the swap
tk.Button(window, text='swap', command=random_swap).pack()
tk.Button(window, text='sort', command=sort).pack()
xstart = 5
xend = 15
canvas = tk.Canvas(window, width='900', height='900')
canvas.pack()
barList = []
lengthList = []
Y = 5
for x in range(1,60):
bar = canvas.create_rectangle(xstart, Y, xend, 395, fill='red')
barList.append(bar)
xstart += 10
xend += 10
Y += 5
for bar in barList:
x = canvas.coords(bar)
length = x[3]-x[1]
lengthList.append(length)
window.mainloop()
最大的问题是 sort_two 里面有 if
if y2 > y1:
canvas.move(pos_0, x_10-x_00, 0)
canvas.move(pos_1, x_01-x_11, 0)
仅当 y2 > y1
但在 sort_two() 之后你使用 barList
sort_two(pos_1, pos_2)
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
始终替换列表中的元素。
这样你在屏幕上的结果是错误的。
您可以从 sort_two() return True/False 来控制何时更改 barList
if y2 > y1:
canvas.move(pos_0, x_10-x_00, 0)
canvas.move(pos_1, x_01-x_11, 0)
return True
else:
return False
和
if sort_two(pos_1, pos_2):
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
这里是最终代码
我使用简单的计算来替换 canvas
上的元素x1, _, _, _ = canvas.coords(pos_0)
x2, _, _, _ = canvas.coords(pos_1)
diff = x1 - x2
canvas.move(pos_0, -diff, 0)
canvas.move(pos_1, +diff, 0)
我也删除了
else:
break
每次替换后停止动画，它需要一次又一次地单击按钮 sort - 我使用
window.update()
time.sleep(0.1)
因此它会（缓慢地）显示动画直到排序结束，我不必单击按钮 sort
import tkinter as tk
import random
import time
def swap_two_pos(pos_0, pos_1):
"""This does the graphical swapping of the rectangles on the canvas
by moving one rectangle to the location of the other, and vice versa
"""
x1, _, _, _ = canvas.coords(pos_0)
x2, _, _, _ = canvas.coords(pos_1)
diff = x1 - x2
canvas.move(pos_0, -diff, 0)
canvas.move(pos_1, +diff, 0)
def sort_two(pos_0, pos_1):
x1, y1, _, _ = canvas.coords(pos_0)
x2, y2, _, _ = canvas.coords(pos_1)
diff = x1 - x2
# moves each rectangle to the x position of the other; y remains unchanged
if y2 > y1:
canvas.move(pos_0, -diff, 0)
canvas.move(pos_1, +diff, 0)
return True
else:
return False
def rand_sort():
for i in range(50000):
rd1 = random.randint(0, 58)
rd2 = random.randint(0, 58)
pos_1 = barList[rd1]
pos_2 = barList[rd2]
if sort_two(pos_1, pos_2):
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
def sort ():
n = len(barList)
# Traverse through all array elements
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
if sort_two(barList[j], barList[j+1]):
barList[j], barList[j+1] = barList[j+1], barList[j]
window.update()
time.sleep(0.1)
def random_swap():
"""Not a sort yet, but you have the bare bones operations
so the swap is executed
"""
for i in range(500):
rd1 = random.randint(0, 58)
rd2 = random.randint(0, 58)
pos_0 = barList[rd1]
pos_1 = barList[rd2]
swap_two_pos(pos_0, pos_1)
# it is necessary to swap the values in the list too
barList[rd1], barList[rd2] = barList[rd2], barList[rd1]
window = tk.Tk()
window.title('Sorting')
window.geometry('600x400')
# button to command the swap
tk.Button(window, text='swap', command=random_swap).pack()
tk.Button(window, text='sort', command=sort).pack()
xstart = 5
xend = 15
canvas = tk.Canvas(window, width='900', height='900')
canvas.pack()
barList = []
lengthList = []
Y = 5
for x in range(1,60):
bar = canvas.create_rectangle(xstart, Y, xend, 395, fill='red')
barList.append(bar)
xstart += 10
xend += 10
Y += 5
for bar in barList:
x = canvas.coords(bar)
length = x[3]-x[1]
lengthList.append(length)
window.mainloop()