ДЗ 7
Дедлайн 18:10 10.11.2014
Файл с программой должен называться именно так, как указано в задании
- Во всех программах должны быть содержательные имена переменных
- Во всех программах не должно быть строк длиннее 75 символов, а если такие строки возникли, части таких строк нужно выносить в отдельные переменные или функции.
- Функции должны сопровождаться docstring
- Тело любой функции должно иметь длину не более 10 строк
- Программа не должна содержать (в разумных пределах) дублирования кода
Вот здесь https://bitbucket.org/dendik/confetti обитает репозиторий с примерами, которые мы делали в классе.
Сделайте в репозитории папку с названием hw7. Все файлы, относящиеся к этому заданию должны быть в этой папке.
- Вдумчиво и неторопливо прочитайте Chapter 1 и Chapter 2 из первого раздела книги Кормена-Лейзерсона-Ривеста. Задайте нам вопросы про места, которые в книге были вам в этих двух главах непонятны.
(8 баллов) Напишите программу bubblesort.py. В программе опишите функцию, реализующую алгоритм BUBBLESORT так, как он описан в книге. Кроме описания функции программа должна содержать несколько вызовов этой функции с различными списками в качестве аргументов для проверки работоспособности функции.
(8 баллов) Напишите программу sort-tokens.py, которая получает на вход файл со списком токенов, который мы сделали в прошлый раз, и сортирует его, используя один из алгоритмов сортировки, которые мы реализовали в классе.
(10 баллов) Напишите программу radix-sort.py, которая реализует RADIX-SORT, описанный в главе 8, для сортировки целых чисел. Сравните скорость работы radix-sort, какой-нибудь из сортировок, реализованных нами в классе, и сортировки, встроенной в питон (функция sorted), на больших объёмах входных данных (например, списки длиной 1000000 чисел).