Сейчас прохожу курс по алгоритмам и структурам данных от ИТМО. Возник вопрос по скорости сортировки вставками.
Задание было дано следующее:
1. Программа должна считывать числа из текстового файла input.txt (проводится 37 тестов, в каждом последующем тесте количество элементов, которые необходимо отсортировать возрастает).
2. После каждой перестановки в выходной текстовый файл output.txt должно записываться сообщение “Swap elements at indices %d and %d.\n' % (j-1, j)”, где j-1 и j - это индексы переставленных элементов.
3. После того как массив отсортирован в output.txt нужно записать сообщение “No more swaps needed” и отсортированный массив.
Скрины с оригинальным заданием ниже.
Листинг программы:
def main(): import time start = time.time() numbers_list = open(file='input.txt', mode='r').read().split() with open(file='output.txt', mode='w') as f_output: for i in range(1, len(numbers_list)): j = i while j > 1 and numbers_list[j-1] > numbers_list[j]: numbers_list[j], numbers_list[j-1] = numbers_list[j-1], numbers_list[j] f_output.write('Swap elements at indices %d and %d.\n' % (j-1, j)) j -= 1 f_output.write('No more swaps needed.\n') s = ' '.join(numbers_list[1:]) f_output.write(s) f_output.close() end = time.time() print(end-start) main()
Тренировался я на массиве 5 3 1. Чтобы я ни делал, не удалось получить время меньше, чем 0,005 секунд.
Как можно ускорить процесс? Прошу подсказать.