|
| Упражнение #4. |
|
Смоделируйте пример исходного массива длины
N=10, иллюстрирующий описанную ситуацию,
когда на каждой итерации отделяется подмассив с единственной
компонентой. |
Подобные "мелкие неприятности" вызвали появление
ряда модификаций алгоритма быстрой сортировки, в основном связанных
с тактикой выбора барьера на очередной итерации, а также с
ограничением длины интервала снизу.
Именно снизу, поскольку с уменьшением мощности
подмассива начинают все в большей степени сказываться значения
коэффициентов, "растворившихся" в асимптотических оценках
трудоемкости. Иначе говоря, на "коротких" векторах реальное время
работы квадратичных сортировок оказывается меньшим, чем при
выполнении QuickSort. Какое число N скрывает качественная оценка "короткий",
зависит и от деталей реализации алгоритма, и от аппаратных
характеристик компьютера.
Одно из популярных решений состоит в том, чтобы
останавливать рекурсивные вызовы процедуры, как только длина
подмассива уменьшается не до 1, а до некоторого натурального M>1. Эту идею выдвинул Седжвик (Robert
Sedgewick, 1978), предложив и дальнейшую стратегию устранения
остающихся беспорядков, которые присутствуют в неупорядоченных M-подмассивах, возникших на месте исходного
вектора. Собственно механизм заключается в том, что вектор, уже
разделенный на такие подмассивы, подвергается заключительной
обработке с помощью алгоритма сортировки простыми
вставками. Эту разновидность обширного семейства сортировок мы
обсудим ниже.
| Упражнение #5. |
|
Напишите процедуру QuickSort2,
разделяющую входной вектор на подмассивы длиной не больше
заданного значения M, которое также
передается в качестве входного параметра.
|
| Задача #1. Анти-QuickSort |
| Имя входного файла |
input.txt |
| Имя выходного файла |
output.txt |
| Максимальное время работы на одном тесте |
2 секунды |
|
|
На входе программы числовой массив заданной
длины N. Переставить его элементы таким
образом, чтобы выходной массив имел вид, наименее пригодный
для работы алгоритма QuickSort, а именно, на каждой итерации
разделения появлялся бы подмассив единичной длины.
Формат входных данных
В первой строке входного файла находится
число N (1<=N<=1000), затем следуют N элементов массива, все значения которого
различны и лежат в интервале -32768..32767.
Формат выходных данных
Выходной файл должен содержать требуемую
перестановку. Если таких перестановок существует более одной,
то достаточно вывести любую из них.
| Пример входного файла |
Пример выходного файла |
4
10 -7 8 5 |
8 -7 5 10 | |
Назад
|
