Упражнения для программирования¶

1. Проведите эксперимент по тестированию различий между последовательным и бинарным поиском на списке случайных целых чисел.
2. Используйте функции бинарного поиска, данные в тексте (итеративную и рекурсивную). Сгенерируйте упорядоченный список случайных целых чисел и сделайте сравнительный анализ для каждой. Какие результаты вы получили? Можете ли вы их объяснить?
3. Реализуйте бинарный поиск, используя рекурсию без оператора среза. Напоминаем, что для этого вам нужно передать в функцию начальный и конечный индексы подсписка. Сгенерируйте упорядоченный список случайных значений и проведите сравнительный анализ.
4. Реализуйте метод len (__len__) для хэш-таблицы реализации АТД Map.
5. Реализуйте метод in (__contains__) для хэш-таблицы реализации АТД Map.
6. Как вы можете удалять элементы из хэш-таблицы, использующей цепочки для разрешения коллизий? А если используется открытая адресация? Какие особые случаи должны обрабатываться? Реализуйте метод del для класса HashTable.
7. Для хэш-таблицы реализации отображения выбран размер 11. Если таблица полна, его требуется увеличить. Переделайте метод put таким образом, чтобы таблица автоматически меняла размер, когда загрузочный фактор достигает предопределённого значения (его вы можете определить, основываясь на оценке “загрузка vs производительность”).
8. Реализуйте квадратичное сканирование как технику повторного хэширования.
9. Создайте список из 500 целых, используя генератор случайных чисел. Проведите сравнительный анализ, используя любые алгоритмы сортировки из этой главы. Каковы различия в скорости выполнения?
10. Реализуйте сортировку пузырьком, руководствуясь аналогичным заданием.
11. Пузырьковая сортировка может быть изменена, чтобы “пузыриться” в обоих направлениях. Первый проход перемещает “верх” списка, второй - “низ”. Этот альтернативный шаблон продолжается, пока не иссякнет необходимость в проходах. Воплотите этот вариант и опишите, в каких обстоятельствах он может использоваться.
12. Реализуйте сортировку выбором, используя аналогичное задание.
13. Проведите сравнительный анализ для сортировки Шелла, используя различные наборы инкрементов на одном и том же списке.
14. Реализуйте функцию mergeSort без оператора среза.
15. Одним из способов улучшить быструю сортировку является использование сортирки вставками на списках малой длины (назовите её “пределом деления”). Почему это работает? Реализуйте заново быструю сортировку и используйте её для сортировки списка случайных целых чисел. Проанализируйте результат использования различных величин для предела деления.
16. Реализуйте метод “медианы трёх” для выбора опорного значения, как модификацию quickSort. Запустите эксперимент по сравнению двух техник.