Как посчитать количество свопов, сделанных в сортировке вставок? - PullRequest
Новая
       38

Как посчитать количество свопов, сделанных в сортировке вставок?

1 голос
/ 17 мая 2019

Я пытаюсь подсчитать, сколько раз Insertion Sort выполняет обмен или сортировку значения в массиве.Где я должен увеличить счетчик подкачки?

Это на Python 3, и я проверил несколько отступов, но ни один из них не работал.Кроме того, безрезультатно, я искал ответы на разных сайтах, включая переполнение стека. 

def insertionsort(array):
    swapsmade = 0
    checksmade = 0
    for f in range(len(array)):
        value = array[f]
        valueindex = f
        checksmade += 1
        # moving the value
        while valueindex > 0 and value < array[valueindex-1]:
            array[valueindex] = array[valueindex-1]
            valueindex -= 1
            checksmade += 1
        swapsmade += 1 #  FIX THIS
        array[valueindex] = value
    print(array)
    swapsnchecks = "{} swaps were made. {} checks were made.".format(swapsmade, checksmade)
    return swapsnchecks

Проблема с тем, как я разместил счетчик, возникает, когда я использую отсортированный список, например, сдесять целых чисел (то есть [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]).Я ожидал, что на выходе получится 0 swaps were made. 55 checks were made., но в итоге получится 10 swaps were made. 55 checks were made.

1 Ответ

2 голосов
/ 17 мая 2019

Вам просто нужно вставить свой счетчик в цикл while следующим образом: 

def insertionsort(array):
    swapsmade = 0
    checksmade = 0
    for f in range(len(array)):
        value = array[f]
        valueindex = f
        checksmade += 1
        # moving the value
        while valueindex > 0 and value < array[valueindex-1]:
            array[valueindex] = array[valueindex-1]
            valueindex -= 1
            checksmade += 1
            swapsmade += 1 #  Move inside the while loop
        array[valueindex] = value
    print(array)
    swapsnchecks = "{} swaps were made. {} checks were made.".format(swapsmade, checksmade)
    return swapsnchecks

Например: 

print(insertionsort([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))
print(insertionsort([2, 1, 3, 4, 5, 6, 7, 8, 9, 10]))
print(insertionsort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]))

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
0 swaps were made. 10 checks were made.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
1 swaps were made. 11 checks were made
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
45 swaps were made. 55 checks were made.
...