Оптимизация алгоритмов сортировки Python

def MinimumSwaps(Queue):
        MinSwaps = 0
        for i in range(len(Queue) - 1):
            if Queue[i] != i+1:
                for j in range(i+1,len(Queue)):
                    if Queue[j] == i+1:
                        Queue[i], Queue[j] = Queue[j], Queue[i]
                        MinSwaps += 1
                        break
            else:
                continue
        return MinSwaps

def main():
    Result = MinimumSwaps([7, 1, 3, 2, 4, 5, 6])
    print(Result)  
if __name__ == "__main__":
    main()

Вопрос: Вам дан неупорядоченный массив, состоящий из последовательных целых чисел [1, 2, 3, …, n] без дубликатов. Вы можете поменять местами любые два элемента. Вам нужно найти минимальное количество свопов, необходимых для сортировки массива в порядке возрастания.

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

Вместо поиск для значения, которое принадлежит Queue[i] чтобы поменять его там, просто поменяйте местами значение, которое является там, где это принадлежит:

def MinimumSwaps(Queue):
    MinSwaps = 0
    for i in range(len(Queue) - 1):
        while Queue[i] != i + 1:
            j = Queue[i] - 1
            Queue[i], Queue[j] = Queue[j], Queue[i]
            MinSwaps += 1
    return MinSwaps

Это улучшает производительность до $ O (1) $ для использования значения вместо $ O (п) $ для поиска. И таким образом общая производительность $ O (п) $ вместо вашего оригинала $ O (п ^ 2) $. По-прежнему используется только O (1) дополнительного места.

Ваш код $ O (п ^ 2) $ из-за внутреннего цикла.

for j in range(i+1,len(Queue)):
    if Queue[j] == i+1:
       # inner

Мы можем изменить это на $ O (1) $ сделав таблицу поиска, где $ i $местонахождение. Мы можем создать словарь для хранения этих запросов.

indexes = {value: index for index, value in enumerate(Queue)

Затем мы можем просто поменять эти индексы на ваш существующий внутренний код, чтобы получить $ O (п) $ спектакль.

def MinimumSwaps(Queue):
    indexes = {value: index for index, value in enumerate(Queue)}
    MinSwaps = 0
    for i in range(len(Queue) - 1):
        i_value = Queue[i]
        if i_value != i+1:
            j = indexes[i+1]
            j_value = Queue[j]
            Queue[i], Queue[j] = Queue[j], Queue[i]
            indexes[i_value], indexes[j_value] = indexes[j_value], indexes[i_value]
            MinSwaps += 1
        else:
            continue
    return MinSwaps

Возможная производительность таблицы достигается за счет использования словаря в качестве таблицы поиска, а не списка. Хотя оба имеют одинаковую алгоритмическую сложность. Чтобы решить эту проблему, мы можем просто построить indexes в виде списка.

indexes = [None] * len(Queue)
for index, value in enumerate(Queue):
    indexes[value] = index