Оптимизировать программу по времени

Question

Из файла input.txt считать первой строкой n(количество) и второй строкой сами числа. В output.txt вывести такой текст, как в примере. Надо выбрать такой метод сортировки, который будет быстрее всего с помощью свопа это делать. Я решила сделать сортировку выбором, но у меня падает тест при n+-5000.

input.txt
5
3 1 4 2 2

output.txt
Swap elements at indices 1 and 2.
Swap elements at indices 2 and 4.
Swap elements at indices 3 and 5.
No more swaps needed.

with open('input.txt', 'r', encoding='utf-8') as f:
    n = int(f.readline())
    arr = list(map(int, f.read().split()))
    with open('output.txt', 'w', encoding='utf-8') as f1:
        strings=[]
        for i in range(0, len(arr) - 1):
            smallest = i
            for j in range(i + 1, len(arr)):
                if arr[j] < arr[smallest]:
                    smallest = j
            arr[i], arr[smallest] = arr[smallest], arr[i]
            string="Swap elements at indices "
            if i<smallest:
                strings.append(string + str(i+1)+ " and " + str(smallest+1)+"."+'\n')
            elif smallest>i:
                strings.append(string + str(smallest+1) + " and " + str(i+1)+"."+'\n')
with open('output.txt', 'w', encoding='utf-8') as f1:
    f1.write("".join(map(str, strings)))
    f1.write("No more swaps needed.")

Answer 1

Вы можете сначала отсортировать изначальный массив, а потом для очередного элемента проверять, равен ли текущий элемент массива элементу в отсортированном массиве, и если нет, то менять текущий с нужным местами.

n = 5
array = [3, 1, 4, 2, 2]
sort_array = sorted([(array[i], i) for i in range(n)])

for i in range(n):
    if sort_array[i][0] != array[i]:
        print('swap', i, sort_array[i][1])
        array[i], array[sort_array[i][1]] = array[sort_array[i][1]], array[i]

Если я не напутал, то алгоритм такой.

БЛОГ НА HUSL

Оптимизировать программу по времени

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