Использование сортировки выбора для сортировки массива в Python. Как я могу оптимизировать?

Question

Работая над этим испытанием на HackerRank и получил этот код для прохождения 10 из 15 тестовых случаев. Это происходит из-за ошибки тайм-аута, которая является способом, который HackerRank сообщает вам, что алгоритм не оптимизирован. Как я могу оптимизировать этот код для работы с большими входными данными?

Цель состоит в том, чтобы выяснить минимальное количество перестановок, необходимых для сортировки несортированного массива.

Обновление : каждый элемент в массиве отличается.

def minimum_swaps(arr):
"""Returns the minimum number of swaps to re-oder array in ascending order."""

    swaps = 0
    for val in range(len(arr) - 1, 0, -1):

        # Index of max value
        max_pos = 0
        for index in range(1, val + 1):

            if arr[index] > arr[max_pos]:
                max_pos = index

        # Skip if value is already in sorted position
        if max_pos == val:
            continue

        arr[val], arr[max_pos] = arr[max_pos], arr[val]
        swaps += 1

    return swaps

Answer 1

Краткий ответ: реализовать сортировку слиянием. Используемый вами алгоритм пузырьковой сортировки имеет время выполнения O (n ^ 2), а сортировка слиянием имеет время выполнения O (log_2 (n)).

Answer 2

Посмотрите на код. Имеет 2 вложенных цикла:

• Внешний цикл перебирает позиции val.
• Внутренний цикл находит индекс значения, который должен быть в индексе val, т.е. max_pos.

Требуется много времени, чтобы найти индекс. Вместо этого я вычислю индекс каждого значения и сохраню его в dict.

index_of = {value: index for index, value in enumerate(arr)}

(обратите внимание, что поскольку все значения в arr различны, дублирующихся ключей быть не должно)

А также подготовьте отсортированную версию массива: таким образом легче найти максимальное значение, вместо того, чтобы циклически перемещаться по массиву.

sorted_arr = sorted(arr)

Затем сделайте все остальное, как в исходном коде: для каждого посещенного индекса используйте sorted_arr, чтобы получить максимум, или index_of, чтобы получить его текущий индекс, если он неуместен, то поменяйте местами. Не забудьте обновить index_of dict при замене тоже.

Алгоритм принимает O(n) операций (включая dict индексирование / изменение), плюс стоимость сортировки n элементов (что составляет около O(n log n)).

---

Примечание. Если массив arr содержит только целые числа в небольшом диапазоне, может быть быстрее сделать массив index_of вместо dict.