Python-сообщество

Привет, всем!

Сейчас прохожу курс по алгоритмам и структурам данных от ИТМО. Возник вопрос по скорости сортировки вставками.

Задание было дано следующее:

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()

Отредактировано albertalexandrov (Сен. 7, 2017 11:48:28)

Прикреплённый файлы:
2.jpg (134,3 KБ)

Первое, что бросается в глаза это вот

 int(numbers_list[j-1]) > int(numbers_list[j])

Зачем вы кастуете к инту в цикле? Сделайте это один раз выше цикла.

albertalexandrov

 s = ''
s += ' '.join(numbers_list[1:])

wtf???

Отредактировано albertalexandrov (Сен. 7, 2017 11:47:51)

albertalexandrov
для последующей записи в файл за один раз.

Ваша строка все равно будет записана побайтно. Смысла в этом нет.

albertalexandrov
Забудьте, тест показывает, что выигрыша по скорости нет, питоний цикл уничтожает все выгоды.