在递归合并排序中跟踪调用和比较的数量
在递归合并排序中跟踪调用和比较的数量
提问于 2021-06-18 05:30:00
我试图在不使用全局变量的情况下跟踪merge()期间对merge_sort()的调用次数和总的比较次数。我下面的代码正确地计算了调用和比较的数量。如果不使用全局变量，我应该怎么做？
import numpy as np
call = 0
compare = 0
def merge_sort(array):
global call # update global
call += 1
n = len(array)
if n <= 1:
return array
arr1 = merge_sort(array[0:n // 2])
arr2 = merge_sort(array[n // 2:n])
new_arr = merge(arr1, arr2)
return new_arr
def merge(arr1, arr2):
new_arr = np.empty(len(arr1) + len(arr2), dtype=int)
ind = 0
i = 0
j = 0
com_num = 0 # Count comparisons in this call
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
com_num += 1 # +1
new_arr[ind] = arr1[i]
i += 1
ind += 1
else:
com_num += 1 # +1
new_arr[ind] = arr2[j]
j += 1
ind += 1
while i < len(arr1):
new_arr[ind] = arr1[i]
i += 1
ind += 1
while j < len(arr2):
new_arr[ind] = arr2[j]
j += 1
ind += 1
global compare # update global
compare += com_num
return new_arr回答 1
Stack Overflow用户
发布于 2021-06-18 12:23:33
这就是我要做的：
def merge_sort(array):
'''Performs merge sort on a given array, and outputs number of
calls and comparisons.'''
sorted_array, calls, comps = _merge_sort(array, 0, 0)
print("Made %d calls and %d comparisons." % (calls, comps))
return(sorted_array)
def _merge_sort(array, calls, comps):
calls += 1
n = len(array)
# Empty or singleton arrays are sorted by definition.
if n <= 1:
return (array, calls, comps)
# Otherwise we recursively merge sort.
else:
left_array, calls, comps = _merge_sort(array[:n//2], calls, comps)
right_array, calls, comps = _merge_sort(array[n//2:], calls, comps)
sorted_array, comps = _merge(left_array, right_array, comps)
return (sorted_array, calls, comps)
def _merge(arr1, arr2, comps):
'''Merges two sorted lists into a bigger sorted list.'''
# NOTE: You can do this with bisect.insort, but I'm assuming you want to
# write your own "first-principles" algorithm, so I didn't use that.
output_array = []
arr1_len = len(arr1)
arr2_len = len(arr2)
# Merge the lists by comparing elements.
i = 0
j = 0
while i < arr1_len and j < arr2_len:
comps += 1
if arr1[i] < arr2[j]:
output_array.append(arr1[i])
i += 1
else:
output_array.append(arr2[j])
j += 1
# One of the lists will now have been exhausted, so we can append
# whatever remains.
output_array += arr1[i:] + arr2[j:]
return (output_array, comps)在这里，我使用了两个以下划线开头的“私有”方法。当使用需要在调用之间跟踪内部变量的递归时，这是非常标准的，因此避免让函数的用户提供这些变量。
我在这里也没有使用NumPy，只是为了让它尽可能通用。你可以进去，把它放在你认为合适的地方。此外，我还做了一些通用的代码清理。特别是，请参阅_merge函数开头的注释。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/68026752
复制相关文章
相似问题
腾讯云开发者
