2024
2023
2022
2021
2020
2019
2018
2017
Алгоритмы сортировки
* (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 балла) Напишите программу. Программа генерирует наборы входных массивов разной длины разными методами: полностью упорядоченный массив, массив, в котором только один элемент стоит не на месте, массив, состоящий из нескольких кусков, каждый из которых упорядочен, массив, в котором элементы идут примерно по возрастанию, – все те же методы для элементов по убыванию, и массив из полностью случайных элементов. Программа реализует сортировку тремя алгоритмами: пузырьком, слиянием, сортировкой. Программа генерирует каждым методом массивы длины 500, 1000, ... 100000 и для каждого типа массивов для каждой длины пишет время, которое требуется каждому алгоритму сортировки для того, чтобы отсортировать массив. Программа должна иметь параметры командной строки, которые позволяют выбирать диапазоны, в которых меняются длины массивов, выбирать типы массивов, алгоритмы сортировки.
Подсказки
Для работы со временем в питоне есть модуль 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 # печатаем разность между временем начала и конца