1. Сортировка, как и любое другое мощное средство, часто используется там, где ее не следует использовать, и не используется там, где без нее не обойтись. Объясните, как можно недооценить или переоценить важность сортировки при получении статистических данных (минимум, максимум, среднее, медиана и мода распределения) для некоторого массива вещественных чисел.
2. [R. Sedgewick] Ускорьте схему разбиения Ломуто (Lomuto), используя элемент х[1] в качестве маркера. Покажите, как эта функция позволяет избавиться от вызова swap после цикла.
3. Какими экспериментами можно найти оптимальное значение cutoff в некоторой системе?
4. Хотя в среднем быстрая сортировка требует 0(log л) памяти на стеке, в худшем случае может потребоваться объем памяти 0(п). Объясните, откуда проистекает этот недостаток, и постарайтесь избавиться от него.
5. [М. D. Mcllroy] Покажите, как можно использовать схему разбиения Ломуто для сортировки битовых строк переменной длины за время, пропорциональное сумме их длим.
6. Используйте методы, описанные в этой главе, для реализации других алгоритмов сортировки. Сортировка выбором помещает наименьший элемент в х[0], затем наименьший из оставшихся в х[1] итак далее. Сортировка Шелла (с уменьшающимся инкрементом) работает аналогично сортировке вставкой, но элементы сдвигаются на h позиций, а не на одну. Начальное значение h затем уменьшается в ппопегсе паботьт
7. Реализации программ сортировки из этой главы можно найти на веб-сайте книги. Измерьте время их работы в вашей системе и сведите результаты в таблицу, аналогичную табл. 11.2.
8. Набросайте руководство пользователю вашей системы по выбору метода сортировки. Метод должен учитывать важность времени выполнения, требуемой памяти, времени программиста (затрачиваемого на разработку и обслуживание программы), общность (что, если нужно отсортировать символьные строки, в которых записаны римские числа?), стабильность (элементы с одинаковыми ключами должны оставаться в исходном порядке), особенности входных данных и другие. В качестве теста можете испробовать это руководство на задаче из главы 1.
9. Напишите программу нахождения k-то минимума в массиве х[0. .п-1] за время О(п). Допускается перестановка элементов.
10. Проведите эксперименты и постройте диаграмму времени работы быстрой сортировки на различных входных данных.
11. Напишите функцию разбиения с «широким главным элементом», постусловие которой будет таким:
Как можно включить такую функцию в программу быстрой сортировки?
12. Изучите методы сортировки, используемые в обычной жизни (сортировка почты, разменные автоматы и другие).
13. Программы быстрой сортировки из этой главы выбирают центральный элемент случайным образом. Изучите возможные варианты, включая выбор медианы по некоторому подмножеству исходного массива.
14. Программы быстрой сортировки, рассматриваемые в данной главе, описывают подмножество с помощью двух целочисленных индексов. Это необходимо в языках типа Java, в которых указатели на элементы массивов отсутствуют. В языках С и C++ можно отсортировать массив целых чисел, используя приведенный ниже формат вызова функции:
void qsortdnt х[]. int n)
для исходного и всех последующих рекурсивных вызовов. Измените алгоритмы этой главы, ориентируясь на использование данного интерфейса.
Опубликовал vovan666
April 17 2013 00:02:48 ·
0 Комментариев ·
3347 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
