Подсчет количества сравнений и перестановок чисел при сортировке

Question

Приложу фрагмент своей программы в виде алгоритма сортировки пузырьковым методом по возрастанию и по спаданию чисел:

import numpy as np
import timeit


def bubble_sort(arr):
    len_arr = len(arr)
    for i in range(len_arr):
        for j in range(0, len_arr - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


def reversed_bubble_sort(arr):
    len_arr = len(arr)
    for i in range(len_arr):
        for j in range(0, len_arr - 1 - i):
            if arr[j] < arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


arr = np.empty(1000, dtype=int)
print(f'Non-sorted array: \n {arr}')

reverse_check = input('Choose the sort order: \n 1.Ascending \n 2.Descending \n')
if reverse_check == '1':
    bubble_sort(arr)
else:
    reversed_bubble_sort(arr)

bubble_sort(arr)
len_arr = len(arr)
print(f'Sorted array: \n {arr}')
t = timeit.timeit('"-".join(str(n) for n in range(100))', number=10000)
print(f"Program was executed by {t} seconds")

Каким образом здесь можно реализовать вывод подсчета количества сравнений чисел и их перестановок в функции сортировки в зависимости от того, какой порядок сортировки выбрал пользователь? Пытался играться с видимостью переменных, разными способами вывода результатов подсчетов, но все безрезультатно. P.S знаю, что скорее всего ответ будет слишком простым и очевидным, но я только изучаю функции, а ответов на подобные вопросы в гугле найти не смог. Буду благодарен за любую помощь, спасибо.

Answer 1

def bubble_sort(arr):
    num_comp = 0
    num_moves = 0
    len_arr = len(arr)
    for i in range(len_arr):
        for j in range(0, len_arr - 1 - i):
            num_comp += 1
            if arr[j] > arr[j + 1]:
                num_moves += 1
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return num_comp, num_moves

num_comp, num_moves = bubble_sort(arr)

Дополнение.

numpy.empty не создаёт массив псевдослучайных чисел. Эта функция создаёт незаполненный массив заданного размера, в котором лежит мусор. Чтобы создать массив псевдослучайных чисел, пользуйтесь функцией numpy.random.randint:

np.random.randint(low, high, size=n)

БЛОГ НА HUSL

Подсчет количества сравнений и перестановок чисел при сортировке

Ответы (1 шт):