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

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函数，所以请给我看代码示例。我将不胜感激任何帮助。

UPD：我根据@Luke19答案修改了我的代码，但我仍然有错误的值(1000 个要排序的数字、1000 个比较和 2 个交换)。

Answer 1

您的heapify函数返回两个对象，因此您应该使用与heap_sort相同的语法 *：num_swaps, num_comps = heapify(...).如果不这样做，您的num_comps变量将不会在heap_sort中更新。

更新：

请注意，使用全局变量通常并不理想。(例如，你可以在这里和这里找到一些关于这个问题的讨论。通常，如果有一个简单的解决方法，您应该避免使用它们，以便获得不那么容易出错的代码。

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

首先，请注意，每次调用heapify时都需要更新num_swaps和num_comps，即使在内部调用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

因为您要传递heapifynum_swaps和num_comps的当前局部值，所以每次执行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并在函数调用之前直接设置它们的归零。此代码现在有效，并显示正确的排序性能指标。