Добавление счетчика сравнения в сортировку слиянием с рекурсией - PullRequest
Новая
       3

Добавление счетчика сравнения в сортировку слиянием с рекурсией

0 голосов
/ 25 февраля 2020

Я попытался добавить счетчик сортировки слиянием ниже, но после того, как я протестировал его, мои выходные данные отсутствуют. Что я делаю неправильно? Я думаю, что моя проблема исходит из рекурсивного аспекта, если алгоритм, но я не понимаю, как и где именно. Любая обратная связь очень ценится! 

def merge(numbers, i, j, k):
    merged_size = k - i + 1
    merged_numbers = []
    for l in range(merged_size):
        merged_numbers.append(0)
    count = 0
    merge_pos = 0
    left_pos = i
    right_pos = j + 1

    while left_pos <= j and right_pos <= k:
        count = count + 1
        if numbers[left_pos] < numbers[right_pos]:
            merged_numbers[merge_pos] = numbers[left_pos]
            left_pos = left_pos + 1
        else:
            merged_numbers[merge_pos] = numbers[right_pos]
            right_pos = right_pos + 1
        merge_pos = merge_pos + 1

    while left_pos <= j:
        merged_numbers[merge_pos] = numbers[left_pos]
        left_pos = left_pos + 1
        merge_pos = merge_pos + 1
        count = count + 1

    while right_pos <= k:
        merged_numbers[merge_pos] = numbers[right_pos]
        right_pos = right_pos + 1
        merge_pos = merge_pos + 1
        count = count + 1

    merge_pos = 0
    while merge_pos < merged_size:
        numbers[i + merge_pos] = merged_numbers[merge_pos]
        merge_pos = merge_pos + 1
        count = count + 1
    return count


def merge_sort_recursive(numbers, i, k):
    if i < k:
        j = (i + k) // 2
        merge_sort_recursive(numbers, i, j)
        merge_sort_recursive(numbers, j + 1, k)
        merge(numbers, i, j, k)

def merge_sort(numbers):
    merge_sort_recursive(numbers, 0, len(numbers)-1)
...