在Python中使用turtlegraphics实现合并排序算法可视化工具

Question

我是一名 Python 初学者，正在尝试将排序算法可视化器实现为一个项目。我实现了选择排序、插入排序和冒泡排序。我认为他们正确地可视化了他们的算法。但在合并排序中，我遇到了一些关于可视化的问题，并且我无法弄清楚我的代码出了什么问题。算法运行良好，但我无法正确可视化它。

这是我的 Visualizer 和 Block 类。 Block 将列表中的每个元素表示为 Turtle 对象。

from blocks import Block
from turtle import *
import time


class Visualize():
    START_X = -650
    blocks = []

    @classmethod
    def create_screen(cls):
        cls.screen = Screen()
        cls.screen.title('Sorting Algorithms')
        cls.screen.setup(width=1600, height=900, starty=0)
        cls.screen.bgcolor('black')
        cls.screen.tracer(0)
    

    @classmethod
    def show_list(cls, arr):
        for i in range(len(arr)):
            cls.blocks.append(Block(len_coef=arr[i], xcor=(cls.START_X + 15 * i)))
            cls.screen.update()


    @classmethod
    def selection_sort(cls, arr):
        n = len(arr)
        for i in range(n - 1):
            min_index = i
            for j in range(i + 1, n):
                cls.blocks[j].color('red')
                cls.screen.update()
                time.sleep(0.02)
                if arr[j] < arr[min_index]:
                    min_index = j
                cls.blocks[j].color('white')
            arr[min_index], arr[i] = arr[i], arr[min_index]
            cls.blocks[min_index], cls.blocks[i] = cls.blocks[i], cls.blocks[min_index]
            cls.blocks[min_index].setx(cls.START_X + 15 * min_index)
            cls.blocks[i].setx(cls.START_X + 15 * i)
            cls.screen.update()


    @classmethod
    def insertion_sort(cls, arr):
        n = len(arr)
        for i in range(1, n):
            key = arr[i]
            block_key = cls.blocks[i]
            block_key.color('red')
            cls.screen.update()
            j = i - 1
            while j >= 0 and key < arr[j]:
                cls.blocks[j].setx(cls.START_X + 15 * (j + 1))
                cls.blocks[j + 1].setx(cls.START_X + 15 * j)
                cls.blocks[j], cls.blocks[j + 1] = cls.blocks[j + 1], cls.blocks[j]
                cls.screen.update()
                time.sleep(0.02)
                arr[j + 1] = arr[j]
                j -= 1
            block_key.color('white')
            arr[j + 1] = key
    

    @classmethod
    def bubble_sort(cls, arr):
        n = len(arr)
        for i in range(n):
            for j in range(n - i - 1):
                cls.blocks[j].color('red')
                cls.screen.update()
                time.sleep(0.02)
                if arr[j] > arr[j + 1]:
                    cls.blocks[j].setx(cls.START_X + 15 * (j + 1))
                    cls.blocks[j + 1].setx(cls.START_X + 15 * j)
                    cls.blocks[j], cls.blocks[j + 1] = cls.blocks[j + 1], cls.blocks[j]
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    cls.blocks[j + 1].color('white')
                else:
                    cls.blocks[j].color('white')
                cls.screen.update()


@classmethod
    def merge_sort(cls, arr):
        n = len(arr)
        if n > 1: 
            mid = n // 2
            L = arr[:mid]
            R = arr[mid:]

            L_BLOCKS = cls.blocks[:mid]
            R_BLOCKS = cls.blocks[mid:]

            cls.merge_sort(L)
            cls.merge_sort(R)
            
            i = j = k = 0
            while i < len(L) and j < len(R):
                if L[i] < R[j]:
                    L_BLOCKS[i].color('red')
                    cls.screen.update()
                    time.sleep(0.05)
                    L_BLOCKS[i].setx(cls.START_X + 15 * k)
                    L_BLOCKS[i].color('white')
                    cls.blocks[k] = L_BLOCKS[i]
                    arr[k] = L[i]
                    i += 1
                else:
                    R_BLOCKS[j].color('red')
                    cls.screen.update()
                    time.sleep(0.05)
                    R_BLOCKS[j].setx(cls.START_X + 15 * k)
                    R_BLOCKS[j].color('white')
                    cls.blocks[k] = R_BLOCKS[j]
                    arr[k] = R[j]
                    j += 1
                cls.screen.update()
                k += 1
            
            while i < len(L):
                L_BLOCKS[i].color('red')
                cls.screen.update()
                time.sleep(0.05)
                L_BLOCKS[i].setx(cls.START_X + 15 * k)
                L_BLOCKS[i].color('white')
                cls.blocks[k] = L_BLOCKS[i]
                arr[k] = L[i]
                i += 1
                k += 1
                cls.screen.update()

            while j < len(R):
                R_BLOCKS[j].color('red')
                cls.screen.update()
                time.sleep(0.05)
                R_BLOCKS[j].setx(cls.START_X + 15 * k)
                R_BLOCKS[j].color('white')
                cls.blocks[k] = R_BLOCKS[j]
                arr[k] = R[j]
                j += 1
                k += 1
                cls.screen.update()

from turtle import *

TURTLE_SIZE = 20
STRETCH_COEF = 0.5

class Block(Turtle):
    def __init__(self, len_coef, xcor):
        super().__init__()
        self.setheading(90)
        self.shape('square')
        self.shapesize(stretch_len=STRETCH_COEF + (STRETCH_COEF * len_coef), stretch_wid=0.5)
        self.turtle_length, self.turtle_width = ((TURTLE_SIZE * STRETCH_COEF * len_coef), TURTLE_SIZE)
        self.goto(xcor, (-430 + self.turtle_length / 2))
        self.color('white')
        self.penup()

在每个算法中，我对块的处理方式与对数组的处理方式相同。因此，也尝试了合并排序，但它无法正确对可视化中的列表进行排序。 代码可能设计得很奇怪或很糟糕。对此的建议也很棒！

Answer 1

我认为代码有两个问题。第一个问题是，正在排序的值数组与表示这些值的海龟数组分离。您传递要排序的值数组，但假设它们仍然与海龟数组索引相关联，但事实并非如此。为了解决这个问题，我将两者绑定在一起并将它们作为一个单元进行排序。

第二个问题是您没有维护海龟内绝对位置的概念，因此您最终会在最左边海龟的切片上进行所有子处理，而不是在值数组中的等效位置。我们需要在递归堆栈中传递一个偏移量来指示海龟数组索引的相对位置，以便我们移动正确的海龟。

from turtle import Screen, Turtle
from time import sleep

TURTLE_SIZE = 20
STRETCH_COEF = 0.5
VALUE, BLOCK = 0, 1

class Block(Turtle):
    def __init__(self, len_coef, xcor):
        super().__init__()

        self.setheading(90)
        self.shape('square')
        self.shapesize(stretch_len=STRETCH_COEF + STRETCH_COEF * len_coef, stretch_wid=0.5)
        turtle_length = TURTLE_SIZE * STRETCH_COEF * len_coef
        self.goto(xcor, turtle_length/2 - 430)
        self.color('white')
        self.penup()

class Visualize():
    START_X = -650
    blocks = []

    @classmethod
    def create_screen(cls):
        cls.screen = Screen()
        cls.screen.title('Sorting Algorithms')
        cls.screen.setup(width=1600, height=900, starty=0)
        cls.screen.bgcolor('black')
        cls.screen.tracer(0)

        return cls.screen

    @classmethod
    def show_list(cls, arr):
        for i, value in enumerate(arr):
            cls.blocks.append(Block(len_coef=value, xcor=(cls.START_X + 15 * i)))
            cls.screen.update()

    @classmethod
    def merge_sort(cls, arr, offset=0):
        n = len(arr)

        if n <= 1:
            return

        mid = n // 2

        L = list(zip(arr[:mid], cls.blocks[offset:offset + mid]))
        R = list(zip(arr[mid:], cls.blocks[offset + mid:offset + n]))

        cls.merge_sort(L, offset)
        cls.merge_sort(R, offset + mid)

        i = j = k = 0

        while k < n:
            if not (j < len(R)) or i < len(L) and L[i][VALUE] < R[j][VALUE]:
                L[i][1].color('red')
                cls.blocks[k + offset] = L[i][BLOCK]
                arr[k] = L[i][VALUE]
                i += 1
            elif not (i < len(L)) or j < len(R) and not L[i][VALUE] < R[j][VALUE]:
                R[j][1].color('red')
                cls.blocks[k + offset] = R[j][BLOCK]
                arr[k] = R[j][VALUE]
                j += 1

            cls.screen.update()
            sleep(0.02)
            cls.blocks[k + offset].setx(cls.START_X + 15 * (k + offset))
            cls.blocks[k + offset].color('white')
            cls.screen.update()
            k += 1

if __name__ == '__main__':
    from random import sample

    array = sample(range(85), 75)

    screen = Visualize.create_screen()
    Visualize.show_list(array)
    Visualize.merge_sort(array)

    print(array)

    screen.exitonclick()

我进行了其他更改，例如使条件更加复杂，以便将合并代码后的冗余移至主合并代码中。