マージソートカウントの比較

Question

質問は次のとおりです。1）比較をカウントする正しいコードですか？ 2）どのように私は（[1,2,3,4]、number_of_comparisons）コードのようにソートされたリストとカウンター返すことができます。

counter = 0 
def merge_sort(lst): 
"""Sorts the input list using the merge sort algorithm. 

>>> lst = [4, 5, 1, 6, 3] 
>>> merge_sort(lst) 
[1, 3, 4, 5, 6] 
""" 
if len(lst) <= 1: 
    return lst 
mid = len(lst) // 2 
left = merge_sort(lst[:mid]) 
right = merge_sort(lst[mid:]) 
return merge(left, right), counter 

def merge(left, right): 
"""Takes two sorted lists and returns a single sorted list by comparing the elements one at a time. 

>>> left = [1, 5, 6] 
>>> right = [2, 3, 4] 
>>> merge(left, right) 
[1, 2, 3, 4, 5, 6] 
""" 
global counter 
if not left: 
    return right 
if not right: 
    return left 
counter += 1 
if left[0] < right[0]: 
    return [left[0]] + merge(left[1:], right) 
return [right[0]] + merge(left, right[1:]) 


lst = [4, 5, 1, 6, 3] 
print(merge_sort(lst)) 

出力：

([1,3,4,5,6], counter) 

Answer 1

答えは、はい、このコードであり、比較、 の数を数えるが、あなたは明らかにあなたがそれらを

を必要としない場合はここで

は、いくつかの変更があり、あなたがそれらを削除することがカウントしたいですかを理解する必要があります

counter = 0 


def merge_sort(lst): 
    global counter 
    if len(lst) <= 1: 
     counter += 1 # increment counter when we dividing array on two 
     return lst 
    mid = len(lst) // 2 
    left = merge_sort(lst[:mid]) 
    right = merge_sort(lst[mid:]) 
    return merge(left, right) 


def merge(left, right): 
    global counter 
    if not left: 
     counter += 1 # increment counter when not left (not left - is also comparison) 
     return right 
    if not right: 
     counter += 1 # the same as above for right 
     return left 
    if left[0] < right[0]: 
     counter += 1 # and the final one increment 
     return [left[0]] + merge(left[1:], right) 
    return [right[0]] + merge(left, right[1:]) 


lst = [4, 5, 1, 6, 3] 
# also you don't need to return counter since you are using global value 
print(merge_sort(lst), counter) 

Also you may try to look here!

Answer 2

という方法で解決策を私を見つけた：

def merge_sort(input_array): 
counter = 0 

if len(input_array) <= 1: 
    return input_array, counter 

left_part = merge_sort(input_array[:len(input_array) // 2]) 
right_part = merge_sort(input_array[len(left_part[0]):]) 

counter += left_part[1] + right_part[1] 

left_ndx = 0 
right_ndx = 0 
final_ndx = 0 

while left_ndx < len(left_part[0]) and right_ndx < len(right_part[0]): 
    counter += 1 
    if left_part[0][left_ndx] < right_part[0][right_ndx]: 
     input_array[final_ndx] = left_part[0][left_ndx] 
     left_ndx += 1 
    else: 
     input_array[final_ndx] = right_part[0][right_ndx] 
     right_ndx += 1 
    final_ndx += 1 

while left_ndx < len(left_part[0]): 
    input_array[final_ndx] = left_part[0][left_ndx] 
    left_ndx += 1 
    final_ndx += 1 
    counter += 1 

while right_ndx < len(right_part[0]): 
    input_array[final_ndx] = right_part[0][right_ndx] 
    right_ndx += 1 
    final_ndx += 1 
    counter += 1 

return input_array, counter 

ので、出力は次のようになります。

([1,3,4,5,6], counter)