Почему я переоцениваю количество сравнений в этом алгоритме сортировки вставок? - PullRequest
Новая
       28

Почему я переоцениваю количество сравнений в этом алгоритме сортировки вставок?

0 голосов
/ 30 марта 2019

Я пытаюсь подсчитать количество сравнений, выполненных в сортировке вставки. В настоящее время мой счетчик сравнения измеряет больше, чем должен, и я не уверен, почему. 

def compare(data, a, b):
    """Returns True if element at index a > element at index b"""
    return data[a] > data[b]

def swap(data, a, b):
    """Swaps the element at index a with element at index b"""
    data[a], data[b] = data[b], data[a]

def insertion_sort(data):
    """Sorts the list into ascending order"""
    comparison_count = 0
    swap_count = 0
    for index in range(1, len(data)):
        position = index
        while position > 0 and compare(data, position - 1, position):
            comparison_count += 1
            swap(data, position - 1, position)
            swap_count += 1
            position -= 1
        comparison_count += 1
    print('Length:', len(data), 'Comparisons:', comparison_count, 'Swaps:', swap_count)

Например, сортировка списка 

[50, 63, 11, 79, 22, 70, 65, 39, 97, 48]

пересчитает количество сравнений на единицу.

1 Ответ

0 голосов
/ 30 марта 2019

Если position > 0 не соответствует действительности, compare(data, position - 1, position) не оценивается, но вы все равно получаете comparison_count += 1.

Простой способ исправить это и объединить приращения (приобщий более элегантный цикл): 

while position > 0:
    comparison_count += 1

    if not compare(data, position - 1, position):
        break

    swap(data, position - 1, position)
    swap_count += 1
    position -= 1

, что также эквивалентно 

for index in range(1, len(data)):
    for position in range(index, 0, -1):
        comparison_count += 1
        if not compare(data, position - 1, position):
            break

        swap_count += 1
        swap(data, position - 1, position)
...