Вася изучил алгоритм сортировки пузырьком по неубыванию. он решил реализовать его для массива целых чисел [13, 18, 7, 4, 10, 14, 15, 17, 2, 5, 9, 16, 11, 3, 20, 6, 19, 12, 8, 1] так: выбираем два случайных соседних элемента в массиве, если левый больше правого, меняем их местами, иначе ничего не делаем. из любопытства, после каждого обмена он выводил новый массив на экран. через какое-то время на экране оказался массив [4, 7, 2, 5, 10, 9, 13, 11, 3, 14, 6, 15, 12, 8, 1, 16, 17, 18, 19, 20], а компьютер завис. сколько операций обмена было сделано за время работы программы? в качестве ответа укажите одно натуральное число, например, 100. пример. пусть был массив [5, 4, 3, 2, 1], а через некоторое время появился массив [4, 5, 3, 1, 2]. тогда за время работы программы было сделано две операции обмена — поменялись местами числа 5 и 4 и числа 2 и 1.
Массив небольшой, и можно подсчитывать инверсии как угодно.
python 3.5:
before = [13, 18, 7, 4, 10, 14, 15, 17, 2, 5, 9, 16, 11, 3, 20, 6, 19, 12, 8, 1]
after = [4, 7, 2, 5, 10, 9, 13, 11, 3, 14, 6, 15, 12, 8, 1, 16, 17, 18, 19, 20]
def countInversions(arr):
counter = 0
for i in range(len(arr) - 1):
for j in range(i + 1, len(arr)):
if arr[i] > arr[j]:
counter += 1
return counter
print(countInversions(before) - countInversions(after))
ответ: 60.