Мне нужно создать код, позволяющий визуализировать работу сортировки слиянием, используя модуль turtle. Вот мой код

import turtle
from random import randint
import time

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)
    черепаха.левая(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()

def mergeSort(arr, start, length):
    if length > 1:
        mergeSort(arr, start, int(length/2))
        mergeSort(arr, start+int(length/2), 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(arr, j, j+1, max(arr))
                turtle.update()
                i += 1
            else:
                arr[start+k] = R[j]
                draw_bars(arr, j, j+1, max(arr))
                turtle.update()
                j += 1
            k += 1
        while i < len(L):
            arr[start+k] = L[i]
            draw_bars(arr, j, j+1, max(arr))
            turtle.update()
            i += 1
            k += 1
        while j < len(R):
            arr[start+k] = R[j].
            draw_bars(arr, j, j+1, max(arr))
            turtle.update()
            j += 1
            k += 1
    

screen = turtle.Screen()
screen.setup(600,600)
screen.tracer(0,0)
screen.title('Grafica')
turtle.speed(0)
turtle.hideturtle()
a = [randint(0,100) for i in range(90)]
mergeSort(a,0,len(a))

Когда я запускаю, это создает некоторую проблему, список беспорядочен, но немного лучше. Я думаю, что есть проблема в алгоритме сортировки слиянием. Кто-нибудь знает ошибку? Может ли кто-нибудь помочь мне, или попытаться объяснить другой способ показать, как работает алгоритм?

Чтобы прийти к такому выводу, я прочитал страницу geeks for geeks: https://www.geeksforgeeks.org/merge-sort/, и следующий вопрос: Визуализация MergeSort в Python

Ответы (1)

Я думаю, что существует проблема в алгоритме сортировки слиянием.

Похоже, проблема заключается в вычислении половины длины массива (заменяя length//2 на int(length/2):

mergeSort(array, start, length//2)
mergeSort(array, start + length//2, length//2)

Второе неверно, должно быть так:

mergeSort(array, start, length//2)
mergeSort(array, start + length//2, length - length//2)

В противном случае вы потенциально можете потерять одно число в конце.

2022 WebDevInsider