时间戳

首页 > 解决方案 > 计算堆排序中比较和排列的次数

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

问题描述

我正在尝试计算堆排序算法中的比较和交换次数（相应的 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 个交换）。

标签： pythonfunctionsortingheapsort

解决方案

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

更新：

请注意，使用全局变量通常并不理想。（例如，您可以在此处和此处找到有关该问题的一些讨论。）通常，如果有一种简单的解决方法，您应该避免使用它们，以减少容易出错的代码。

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

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

因为您传递的是andheapify的当前本地值，所以每次您都将更新这些变量的本地值。num_swapsnum_compsnum_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

希望这可以帮助！让我知道是否清楚。

推荐阅读