计算堆排序中比较和排列的次数

Question

我正在尝试计算堆排序算法中比较和交换的次数（相应地 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 函数，所以请向我展示代码示例。如有任何帮助，我将不胜感激。

更新：我根据@Luke19 的回答修改了我的代码，但我仍然有错误的值（1000 个数字要排序，1000 次比较和 2 次交换）。

Answer 1

你的 heapify 函数 returns 两个对象，所以你应该使用与 heap_sort*: num_swaps, num_comps = heapify(...) 相同的语法。如果您不这样做，您的 num_comps 变量将不会在 heap_sort.

内更新

更新：

请注意，使用全局变量通常并不理想。（例如，您可以找到关于 here and here 的一些讨论。）通常，如果有一个简单的解决方法，您应该避免使用它们，以使代码不易出错。

因此，我将为您提供更详细的说明，说明如何在不使用全局变量的情况下修复代码：

首先，请注意 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

因为您要将 num_swaps 和 num_comps 的当前本地值传递给 heapify，所以每次您这样做 num_swaps, num_comps = heapify(...,num_swaps, num_comps) 时，您将更新您的本地值那些变量。

您应该对 heap_sort 函数中对 heapify 的调用执行相同的操作：

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

希望这对您有所帮助！让我知道是否清楚。

Answer 2

我解决了这个问题，现在我有了这样的代码：

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 并在函数调用之前直接设置它们的归零。此代码现在可以工作并显示正确的排序性能指标。

计算堆排序中比较和排列的次数

Сounting the number of comparisons and permutations in heapsort

python

sorting

function

heapsort