Подсчет количества сравнений и перестановок в heapsort

Question

Я пытаюсь подсчитать количество сравнений и перестановок в алгоритме heapsort (num_comps и num_swaps соответственно):

import numpy as np
import timeit


def heapify(arr, len_arr, i):
    num_swaps = 0
    num_comps = 0
    maxima = i
    l = 2 * i + 1
    r = 2 * i + 2
    num_comps += 1
    if l < len_arr and arr[i] < arr[l]:
        maxima = l
    num_comps += 1
    if r < len_arr and arr[maxima] < arr[r]:
        maxima = r
    if maxima != i:
        num_swaps += 1
        arr[i], arr[maxima] = arr[maxima], arr[i]
        heapify(arr, len_arr, maxima)
    return num_swaps, num_comps


def heap_sort(arr):
    num_swaps = 0
    num_comps = 0
    len_arr = len(arr)
    for i in range(len_arr, -1, -1):
        heapify(arr, len_arr, i)
    for i in range(len_arr - 1, 0, -1):
        num_swaps += 1
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return num_swaps, num_comps


flag = input("If you wanna randomize entered data, press 'Enter'. To enter manually press any other key: ")

if flag == '':
    arr = np.random.randint(-10000, 10000, 1000)
else:
    while True:
        try:
            arr = []
            for i in range(10):
                a = int(input(f'Enter {i + 1} element: '))
                arr.append(a)
            break
        except ValueError:
            print("Input an integer!")
print(f'Non-sorted array: \n {arr}')

num_comps, num_swaps = heap_sort(arr)

len_arr = len(arr)
print(f'Sorted array: \n {arr}')
print(num_comps, 'comparisons were executed')
print(num_swaps, 'swaps were executed ')
t = timeit.timeit('"-".join(str(n) for n in range(100))', number=10000)
print(f"Program was executed by {t} seconds")

Мой код работает, но отображает неправильные значения. Я знаю, что делаю что-то не так, но не могу понять, что именно. Я только изучаю python функций, поэтому, пожалуйста, покажите мне примеры кода. Я был бы благодарен за любую помощь.

UPD: я изменил свой код в соответствии с ответом @ Luke19, но у меня все еще есть неправильные значения (1000 чисел для сортировки, 1000 сравнений и 2 перестановки).

Answer 1

Я исправил эту проблему, и теперь у меня есть такой код:

import numpy as np
import timeit


def heapify(arr, len_arr, i):
    global num_swaps
    global num_comps
    maxima = i
    l = 2 * i + 1
    r = 2 * i + 2
    num_comps += 1
    if l < len_arr and arr[i] < arr[l]:
        maxima = l
    num_comps += 1
    if r < len_arr and arr[maxima] < arr[r]:
        maxima = r
    if maxima != i:
        num_swaps += 1
        arr[i], arr[maxima] = arr[maxima], arr[i]
        heapify(arr, len_arr, maxima)



def heap_sort(arr):
    global num_swaps
    global num_comps
    len_arr = len(arr)
    heapify(arr, len_arr, 0)
    for i in range(len_arr, -1, -1):
        heapify(arr, len_arr, i)
    for i in range(len_arr - 1, 0, -1):
        num_swaps += 1
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)



flag = input("If you wanna randomize entered data, press 'Enter'. To enter manually press any other key: ")

if flag == '':
    arr = np.random.randint(-10000, 10000, 1000)
else:
    while True:
        try:
            arr = []
            for i in range(10):
                a = int(input(f'Enter {i + 1} element: '))
                arr.append(a)
            break
        except ValueError:
            print("Input an integer!")
print(f'Non-sorted array: \n {arr}')
num_swaps = 0
num_comps = 0
heap_sort(arr)

len_arr = len(arr)
print(f'Sorted array: \n {arr}')
print(num_comps, 'comparisons were executed')
print(num_swaps, 'swaps were executed ')
t = timeit.timeit('"-".join(str(n) for n in range(100))', number=10000)
print(f"Program was executed by {t} seconds")

Я только что добавил глобальный статус к своим переменным в функции num_swaps и num_comps и установил их обнуление непосредственно перед функцией вызов. Этот код работает сейчас и отображает правильные показатели эффективности сортировки.

Answer 2

Ваша функция heapify возвращает два объекта, поэтому вы должны использовать тот же синтаксис, который вы использовали для heap_sort*: num_swaps, num_comps = heapify(...). Если вы этого не сделаете, ваша переменная num_comps не будет обновлена ​​внутри heap_sort.

ОБНОВЛЕНИЕ:

Обратите внимание, что использование глобальных переменных часто не идеально. (Вы можете найти некоторое обсуждение этого здесь и здесь , например.) Обычно, если есть простой способ обойти это, вы должны избегать их, чтобы иметь меньше ошибок. prone code.

Итак, я предоставлю вам более подробное объяснение того, как исправить ваш код без использования глобальных переменных:

Во-первых, обратите внимание, что num_swaps и num_comps необходимо обновляться каждый раз, когда вы звоните heapify, даже когда звоните heapify внутри себя! Однако в исходном коде эти два счетчика обнулялись каждый раз, когда вызывался heapify. Поэтому, чтобы они сохранили свои текущие значения, все, что вам нужно сделать, это включить их в качестве аргументов для heapify, а затем использовать возвращенные значения для обновления исходных.

Вот пример, использующий ваши собственные код:

#notice the change to the function's arguments
def heapify(arr, len_arr, i, num_swaps, num_comps):
    maxima = i

    #etc...

    #then every time you call heapify, pass your current num_swaps and     
    # num_comps then update them by setting them to the returned values:
    if maxima != i:
        num_swaps += 1
        arr[i], arr[maxima] = arr[maxima], arr[i]
        num_swaps, num_comps = heapify(arr, len_arr, maxima, num_swaps, num_comps) #notice the change to the line

    return num_swaps, num_comps

Поскольку вы передаете heapify текущие локальные значения num_swaps и num_comps, каждый раз, когда вы делаете num_swaps, num_comps = heapify(...,num_swaps, num_comps), вы будете обновлять свои локальные значения для этих переменных. .

Вы должны сделать то же самое для вызовов на heapify внутри вашей функции heap_sort:

def heap_sort(arr):
    num_swaps = 0
    num_comps = 0
    len_arr = len(arr)
    for i in range(len_arr, -1, -1):
        num_swaps, num_comps = heapify(arr, len_arr, i, num_swaps, num_comps) #notice the change to this line

    #etc....

    return num_swaps, num_comps

Надеюсь, это поможет! Дайте мне знать, если это понятно.