在 Python 中可视化 MergeSort [英] Visualize MergeSort in Python

问题描述

我想在 python 中制作一个归并排序可视化器.我想使用乌龟模块.要绘制单个条形，我使用函数 draw_bar，而要绘制整个数组，则使用函数 draw_bars.这是代码

I want to make a mergesort visualizer in python. I want to use turtle module. To draw a single bar i use the function draw_bar, and to draw the entire array there is the function draw_bars. Here is the code

def draw_bar(x,y,w,h):
    turtle.up()
    turtle.goto(x,y)
    turtle.seth(0)
    turtle.down()
    turtle.begin_fill()
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.fd(w)
    turtle.left(90)
    turtle.fd(h)
    turtle.left(90)
    turtle.end_fill()

def draw_bars(v,currenti=-1,currentj=-1,M=500):
    turtle.clear()
    x = -250
    n = len(v)
    w = 500/n
    r = 500/M
    for  i in range(n):
        if i == currenti: turtle.fillcolor('red')
        elif i == currentj: turtle.fillcolor('blue')
        else: turtle.fillcolor('gray')
        draw_bar(x,-250,w,v[i]*r)
        x += w
    screen.update()

现在我有了这个归并排序算法:

Now i have this merge sort algorithm:

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        mergeSort(L)
        mergeSort(R)
        i=0
        j=0
        k=0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

现在我需要知道如何放置刷新可视化列表的代码部分.

Now I need to know ho to put the part of the code that refresh the visualised list.

推荐答案

每次更改数组时都需要更新图形，这意味着每次 arr[k] = L[j]

You would need to update your grafics every time your array is changed, meaning after each arr[k] = L[j]

然而，这在您当前的实现中很难做到，因为您的递归函数没有关于它正在操作的更大列表的哪一部分的信息.

This is however difficult to do in your current implementation, because your recursive function has no information about which part of the larger list it is operating on.

我建议更改函数，以便它始终传递完整数组以及它将处理的部分的起始索引和长度:

I would recommend to change the function so that it is always passed the compleat array as well as the start index and length of the part it will be working on:

def mergeSort(arr, start, length):
    if length > 1:
        mergeSort(arr, start, length/2)
        mergeSort(arr, start+length/2, length/2)
        etc.

这样您就可以在每次数组更改时调用 drawbars.

Then you will be able to call drawbars every time, your array changes.

完整代码如下所示:

def mergeSort(arr, start, length):
    if length > 2:
        mergeSort(arr, start, int(length/2))
        mergeSort(arr, start+int(length/2), int(length/2))
    
    print(start+int(length/2))
    L = arr[start:start+int(length/2)]
    R = arr[start+int(length/2):start+length]
    i=0
    j=0
    k=0
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            arr[start+k] = L[i]
            draw_bars(myarray)
            i += 1
        else:
            arr[start+k] = R[j]
            draw_bars(myarray)
            j += 1
        k += 1
    while i < len(L):
        arr[start+k] = L[i]
        draw_bars(myarray)
        i += 1
        k += 1
    while j < len(R):
        arr[start+k] = R[j]
        draw_bars(myarray)
        j += 1
        k += 1
        
myarr = [2,345,2456,3456,56,34,5,78,34,5423,26487,324,1,3,4,5]
draw_bars(myarray)
mergeSort(myarr, 0 ,len(myarr))
print(myarr)

这篇关于在 Python 中可视化 MergeSort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！