2024
2023
2022
2021
2020
2019
2018
2017
Сортировки
Можно сдавать только один из вариантов на ваш выбор.
(1 балл) Поучаствуйте в Турнире Ломоносова в качестве старшего по аудитории (включает в себя наблюдение за школьниками чтобы они не списывали и сортировку работ методом слияния). Турнир проходит 30 сентября, в воскресенье. За участие обещают заплатить 400-500 р. Для участия нужно связаться с Машей Трегубовой. Для того, чтобы вам был зачтён балл за участие, вам нужно сообщить нам (преподавателям по алгоритмам) до следующего занятия включительно, что вы будете в этом участвовать.
(1 балл) На бумажке отсортируйте данные массивы пузырьком, слиянием и быстрой сортировкой. Запишите в табличку количество сравнений элементов для каждого алгоритма для каждого массива. Массивы:
- [69, 16, 63, 77, 52]
- [19, 53, 48, 88, 8, 24, 76, 33, 47, 88]
- [93, 84, 80, 36, 100, 6, 8, 53, 48, 4, 95, 32, 23, 49, 88]
(1 балл) Написать программу. Программа получает на вход файл, в котором в одну строку записаны числа через пробел (проверять соответствие файла формату не требуется). Программа сортирует массив алгоритмом быстрой сортировки и пишет элементы массива на экран в порядке возрастания.
(1 балл) Напишите программу. Программа получает на вход файл, в котором в одну строку записаны числа через пробел (проверять соответствие файла формату не требуется). Программа сортирует массив алгоритмом слияния и пишет элементы массива на экран в порядке возрастания.
(2 балла) Напишите программу. Программа получает на вход файл, в котором в одну строку записаны числа через пробел (проверять соответствие файла формату не требуется). Программа реализует сортировку двумя алгоритмами из списка: пузырьком, слиянием, быстрой сортировкой. Программа измеряет время для сортировки входного массива каждым из реализованных алгоритмов, проверяет, что обе сортировки выдали один и тот же результат, и пишет на экран отсортированный в порядке возрастания элементов массив и получившиеся времена работы.
(3 балла) Напишите программу. Программа генерирует наборы входных массивов разной длины разными методами: полностью упорядоченный массив, массив, в котором только один элемент стоит не на месте, массив, состоящий из нескольких кусков, каждый из которых упорядочен, массив, в котором элементы идут примерно по возрастанию, – все те же методы для элементов по убыванию, и массив из полностью случайных элементов. Программа реализует сортировку тремя алгоритмами: пузырьком, слиянием, сортировкой. Программа генерирует каждым методом массивы длины 5, 10, ... 100, и для каждого типа массивов для каждой длины пишет время, которое требуется каждому алгоритму сортировки для того, чтобы отсортировать массив. Программа должна иметь параметры командной строки, которые позволяют выбирать диапазоны, в которых меняются длины массивов, выбирать типы массивов, алгоритмы сортировки.
Подсказки
Для работы со временем в питоне есть модуль datetime. Пример работы с этим модулем:
1 from datetime import datetime
2 # класс datetime в модуле datetime можно использовать напрямую,
3 # но проще создавать объекты этого класса, используя функцию datetime.now()
4 t1 = datetime.now() # запоминаем нынешнее время в переменную t1
5 x = range(100500) # долго думаем
6 t2 = datetime.now() # время после того, как подумали
7 print t1 # печатаем время начала
8 print t2 # время конца
9 print t2 - t1 # печатаем разность между временем начала и конца