Главная Промышленная автоматика.

3.19. Рассмотрим прямоугольный массив. Расположим элементы в каждой строке в порядке возрастания. Затем расположим в порядке возрастания элементы каждого столбца. Докажите, что каждая строка останется упорядоченной.

*3.20. Пусть fli, flj, . . ., а„- последовательность элементов, а р ид - положительные целые числа. Рассмотрим подпоследовательности, образованные выбором каждого р-го элемента. Упорядочим их. Повторим этот процесс для д. Докажите, что подпоследовательности шага р останутся упорядоченными.

**3.21. Рассмотрим нахождение с помощью сравнений наибольшего и второго по величине элемента в п-элементном множестве. Докажите, что для этого необходимо и достаточно п+ f log п ~ -2 сравнений.

**3.22. Покажите, что среднее число сравнений, требуемых для нахождения k-то наименьшего элемента в га-элементной последовательности, не меньше (1+0,75 а(1-а)) п, где a=k/n, а А и га достаточно велики.

**3.23. Покажите, что в худшем случае требуется га+ +MIN (k, n-k+l)-2 сравнений для нахождения k-ro наименьшего элемента в га-элементном множестве.

**3.24. Пусть S - множество, состоящее из га целых чисел. Допустим, что вы можете только складывать его элементы и сравнивать суммы. Сколько требуется сравнений для нахождения при этих условиях наибольшего элемента в S?

*3.25. Алгоритм 3.6 разбивает свой аргумент на подпоследовательности размера 5. Будет ли этот алгоритм работать для других размеров, например 3, 7 или 9? Выберите тот размер, который минимизирует общее число сравнений. На рис. 3.14 указано наименьшее известное число сравнений, достаточное для упорядочения множеств различных размеров. Известно, что для га<12 эти числа оптимальны.

*3.26. Алгоритм 3.5 разбивает данную последовательность на подпоследовательности длины 5, а затем находит медиану медиан. Вместо того, чтобы искать медиану медиан, не будет ли эффективнее найти какой-нибудь другой элемент, например [ k/5 J -й?

Размер л

Число сравнений

Рис. 3.14. Число сравнений, достаточное для упорядочения последовательности из п элементов (наименьшие известные значения).



*3.27. Рассмотрим следующий метод сортировки. Начнем с последовательности, состоящей из одного элемента. В эту последовательность по одному будем вставлять другие элементы с помощью двоичного поиска. Придумайте структуру данных, позволяющую быстро производить двоичный поиск и вставлять элементы. Можете ли вы реализовать эту сортировку за время О (п log п)?

**3.28. Вместо того, чтобы для разбиения множества размера п выбирать произвольный элемент, как мы делали в Быстрсорт или алгоритме 3.7, можно было бы сделать небольшую выборку, скажем, размера s, найти ее медиану и использовать ее, чтобы разбить все множество. Укажите, как надо выбрать s как функцию от п, чтобы минимизировать среднее число сравнении, необходимых для сортировки.

**3.29. Обобщите идею упр. 3.28 так, чтобы минимизировать число сравнений, необходимых для нахождения порядковой статистики. Указание: Извлеките из выборки два элемента, между которыми с большой вероятностью лежит искомый элемент.

3.30. Метод сортировки стабилен, если равные элементы остаются в упорядоченной последовательности в том же относительном порядке, в каком они были в исходной последовательности. Какой из перечисленных ниже алгоритмов стабилен?

(а) СОРТВЗБАЛТЫВАНИЕМ (упр. 3.5)

(б) Сортслиянием (алгоритм 2.4)

(в) Сортдеревом (алгоритм 3.4)

(г) Быстрсорт (алгоритм 3.5)

Проблема для исследования

3.31. Некоторые проблемы, касающиеся числа сравнений, необходимых в определенных ситуациях, все еще не решены. Например, пусть требуется найти k наименьших элементов из п-элементного множества. Случай k=3 рассмотрен Праттом, Яо [1973]. Для п13 неизвестно, оптимальны ли для упорядочения п элементов числа, приведенные в таблице на рис. 3.14. Для малых п оптимальным в смысле числа сравнений является алгоритм сортировки из работы Форда, Джонсона [1959] ).

») Отметим, что окончательное решение задачи о порядке сложности сортировки не получено, а именно не известны ответы на некоторые естественные вопросы. Например, рассмотрим сортировку п натуральных чисел, каждое из которых имеет длину двоичного представления k, на адресной машине с длиной регистров I (k я I - функции от и). Если сортируемые числа подаются на вход поразрядно, то время считывания входных данных (т. е. тривиальная нижняя оценка сложности) есть kn; алгоритмы такой сложности изложены в гл. 3. Пусть теперь сортируемые числа считываются частями длины I, т. е. целыми регистрами. Тогда время считывания входных данных есть kn/l. Если отношение k/l ограничено постоянной, то тривиальная нижняя оценка сложности сортировки имеет вид СП, где с - некоторая постоянная. Вопрос о достижимости (по порядку) таких нижних оценок открыт.- Прим. перев.



Замечания по литературе

Книга Кнута [1973а] представляет собой энциклопедическое руководство по методам сортировки. Сортдеревом берет начало от Уильямса [1964]; некоторые улучшения сделаны Флойдом [1964]. Быстрсорт ввел Хоор [1962]. Улучшения Быстрсорт по схеме упр. 3.28 предложены Синглтоном [1969], а также Фрейзером, Мак-Келларом [1970]. Алгоритм 3.6 для нахождения порядковой статистики, линейный в худшем случае, изложен в работе Блюма, Флойда, Пратта, Ривеста, Тарьяна [1972]. Хейдиан, Соубел [1969] и Пратт, Яо [1973] исследуют число сравнений, необходимое для нахождения некоторых порядковых статистик.

Результат упр. 3.21 получен Кислицыным [1964]. Упр. 3.22, 3.23 и 3.29 взяты из работы Флойда, Ривеста [1973], где также приведена более сильная нижняя оценка, чем та, что указана в упр. 3.22. Упр. 3.19, 3.20 и некоторые обобщения обсуждаются в работах Гейла, Карпа [1970] и Лю [1972]. Интересное приложение сортировки к нахождению выпуклой оболочки множества точек на плоскости дано Грэхемом [1972]. Стабильная сортировка рассмотрена Хорватом [1974].





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 [38] 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0038