Алгоритмы - построение и анализ (1021735), страница 45
Текст из файла (страница 45)
Чтобы получить выходную последовательность, нужно просто выполнить сортировку чисел в каждом кармане, а затем последовательно перечислить элементы каждого кармана. При составлении кода карманной сортировки предполагается, что на вход подается массив А, состоящий из и элементов, и что величина каждого принадлежащего массиву элемента А [г] удовлетворяет неравенству 0 < А [1] < 1. Для работы нам понадобится вспомогательный массив связанных списюв (карманов) В [О..и — Ц; предполагается, что в нашем распоряжении имеется механизм поддержки таких списков.
(Реализация основных операций при работе со связанным списком описана в разделе 10.2.) В22СКЕТ ЯОКТ(А) 1 и — 1еидй [А] 2 аког г' - 1 1о и 3 йо Вставить элемент А[(] в список В[[иА[тЦ] 4 аког 1 — 0 1о и — 1 5 с(о Сортировка вставкой списка В[1] 6 Объединение списков В[0], В[1],..., В(и — 1] Чтобы понять, как работает этот алгоритм, рассмотрим два элемента А [(] и А [2]. Без потери общности можно предположить, что А [г] < А [2]. Поскольку [иА [(Ц < [иА [Я~, то элемент А [г] помещается либо в тот же карман, что и элемент А [2], либо в карман с меньшим индексом. В первом случае элементы 7 4 '[27[ „'7 ;: ~.72( ь [с;~[ 7 [2![ 7 '2 2! , 7 — 7„-[ «с«[.63« в «7 .ч --'"', *«27«Г — ' — ~",«и««' ° -3" 2 «[ — « — «[ '2772 —; — э 7 26[, « ' « —,'-~ЪЛ,~ ~ : " -2- .Г«ьз( [,!-.2Т-+ «-Я~~7 Я [ '[ г- 7'1 ''] Часть П.
Сортировка и порядковая статистика 232 Вычисляя математическое ожидание обеих частей этого уравнения и воспользо- вавшись его линейностью, с учетом уравнения (В.21) получаем: и-1 Е[Т(п)] = Е 9(п)+ ) 0(п~) '=о и-1 = 6 (п) + ~~~ Е [О (п~)] = ыо к-1 = О (п) + ~~> 0 (Е [п~]) (8.1) Мы утверждаем, что для всех г = 0,1,...,п — 1 Е [п8] = 2 — 1/п. (8.2) Не удивительно, что каждому 1-му карману соответствует одна и та же величина Е [п~1, поскольку все элементы входного массива могут попасть в любой карман А [г] и А [т] располагаются в нужном порядке благодаря циклу 1ог в строках 4-5. Если же эти элементы попадут в разные карманы, то они разместятся в правильном порядке после выполнения строки 6.
Таким образом, карманная сортировка работает корректно. На рис. 8.4 показано, как с помощью карманной сортировки обрабатывается входной массив, состоящий из 10 чисел. В части а этого рисунка показан входной массив А [1..10]. В части б изображен массив В [0..9], состоящий из отсортированных списков после выполнения строки 5 алгоритма.
В 1-м кармане содержатся величины, принадлежащие полуоткрытому интервалу [г/10, (г + 1)/10). Отсортированная выходная последовательность представляет собой объединение списков В [О], В [1],..., В [9]. Чтобы оценить время работы алгоритма, заметим, что в наихудшем случае для выполнения всех его строк, кроме строки 5, требуется время 0 (п). Остается просуммировать полное время, которое потребуется для и вызовов алгоритма сортировки методом вставок (строка 5).
Чтобы оценить стоимость этих вызовов, введем случайную величину пэ обозначающую количество элементов, попавших в карман В [1]. Поскольку время работы алгоритма сортировки вставкой является квадратичной функцией от количества входных элементов (см. раздел 2.2), время работы алгоритма карманной сортировки равно 233 с равной вероятностью. Чтобы доказать уравнение (8.2), определим для каждого г = О, 1,...,п — 1 и т' = 1, 2,...,п индикаторную случайную величину Х, = 1(А ]т] попадает в (-ый карман). Следовательно, Чтобы вычислить величину Е (п,'], раскроем квадрат и перегруппируем сла- гаемые: Е(п~] =Е х; х; =Е (8.3) 1(я<и я~у ~ ' е [х;,х„] 1(Ь (и /с~у В приведенной выше цепочке уравнений последнее равенство следует из линей- ности математического ожидания. Отдельно оценим обе суммы.
Индикаторная случайная величина Х, равна 1 с вероятностью Цп и О в противном случае, поэтому получаем: Е(Х1] =1.— +О ~1 — -) = —. и ~, п) п Когда й ~ т', величины Х; и Хсь независимы, поэтому можно записать: 1 1 1 Е]ХОХсь] = Е]ХО] Е]хсь] = п п пз Подставив эти величины в уравнение (8.3), получим: 2 1 1 1 Е ~из] = с> — + ~1 ~~1 — = п — +п(п — 1) ° — = 1 п п2 3=1 1Я<и 1<1с<и /сну и — 1 1 + — =2 — —, и и что и доказывает уравнение (8.2).
Используя это выражение в уравнении (8.1), приходим к выводу, что математическое ожидание времени работы алгоритма карманной сортировки равно Глава 8. Сортировка за линейное время и1=~> Х;. 1=1 (Ехс) ] =и [ ЕХ2+ Х с=1 1ЯЯи = )'Е~Х2-1+ ,') 2=1 1Я<и и и ~~~, Хбхсь 2=1 Ь=1 Часть 11. Сортировка и порядковая статистика 234 6(п)+п О (2 — 1/и) = 9 (и). Таким образом, математическое ожидание времени работы алгоритма карманной сортировки в целом линейно зависит от количества входных элементов. Такая зависимость может наблюдаться даже в том случае, когда входные элементы не подчиняются закону равномерного распределения.
Если входные элементы обладают тем свойством, что сумма возведенных в квадрат размеров карманов линейно зависит от количества входных элементов, уравнение (8.1) утверждает, что карманная сортировка этих данных выполняется в течение времени, линейно зависящего от количества данных. Упражнения 8.4-1. Используя в качестве модели рис. 8.4, проиллюстрируйте обработку алгоритмом Висквт 8окт массива А = (079,013,016,064,039,020,089, 0.53, 0.71, 0.42).
8.4-2. Чему равно время работы алгоритма карманной сортировки в наихудшем случае? Какое простое изменение следует внести в этот алгоритм, чтобы его ожидаемое время работы осталось линейным, а время работы в наихудшем случае стало равным О (и 18 и)? *8.4-3. Функция расярсделеиия вероятности Р(х) случайной величины Х определяется с помощью соотношения Р (х) = Рг (Х < х). Предположим, что на вход алгоритма поступает последовательность из п случайных величин ХПХз,...,Х„с непрерывной функцией распределения Р, значение которой вычисляется в течение времени О (1). Покажите, каким образом выполнить сортировку этих величин, чтобы математическое ожидание времени выполнения процедуры линейно зависело от их количества. Задачи 8-1. Нижние оценки для сортировки сравнением в среднем случае В этой задаче мы докажем, что нижняя граница математического ожидания времени работы любого детерминистического или рандомизированного алгоритма сортировки сравнением при обработке и различающихся входных элементов равна П (и 18 и).
Начнем с того„что рассмотрим детерминистическую сортировку сравнением А, которой соответствует дерево решений Тд. Предполагается, что все перестановки входных элементов А равновероятны. а) Предположим, что каждый лист дерева Тд помечен вероятностью его достижения при заданном случайном наборе входных данных. Глава 8. Сортировка за линейное время 235 Докажите, что ровно п1 листьям соответствует вероятность 1/п1, а остальным — вероятность О. б) Пусть Р (Т) — длина внешнего пути дерева решений Т; другими словами, это сумма глубин всех листьев этого дерева. Пусть Т— дерево решений с )с > 1 листьями, а РТ и ВТ вЂ” его левое и правое поддеревья.
Покажите, что Р (Т) = Р (РТ) + Р (ЯТ) + lс. в) Пусть Н (к) — минимальная величина Р (Т) среди всех деревьев решенийТсlс > 1листьями. Покажите,чтод(lс) = шшз«;ь ~(Н(г)+ + Н (1с — г) + к). (Указание: рассмотрите дерево решений Т с )с листьями, на котором достигается минимум. Обозначьте количество листьев в РТ через гс, а количество листьев в ЯТ вЂ” через й — го.) г) Докажите, что для данного )с > 1 и ю' из диапазона 1 < г < )с — 1 функция Г 1к Г + (Й вЂ” г) 1к (Й вЂ” г) достигает минимума при г = Й/2.
Выведите отсюда, что д(к) = й(й18к). д) Докажите, что справедливо соотношение Р (Тд) = й(п! 18(п1)), и выведите отсюда, что математическое ожидание времени сортировки и элементов равно й (и 18 и). А теперь рассмотрим рандаиизированную сортировку В.
Модель дерева решений можно обобщить таким образом, чтобы с ее помощью можно было рассматривать рандомизированные алгоритмы. Для этого в нее нужно включить узлы двух видов: обычные узлы сравнения и узлы "рандомизации", которые моделируют случайный выбор вида Клипом(1, г) в алгоритме В; такой узел имеет г дочерних узлов, каждый из которых в процессе выполнения алгоритма может быть выбран с равной вероятностью. е) Покажите, что для любой рандомизированной сортировки сравнением В существует детерминистическая сортировка сравнением А, в которой в среднем производится не больше сравнений, чем в сортировке В. 8-2. Сортировка на месте за линейное время Предположим, что у нас имеется массив, содержащий п записей с сортируемыми данными, и что ключ каждой записи принимает значения О или 1.
Алгоритм„предназначенный для сортировки такого набора записей, должен обладать некоторыми из трех перечисленных ниже характеристик. 1) Время работы алгоритма равно 0 (и). 2) Алгоритм обладает свойством устойчивости. 236 Часть й. Сортировка и порядковая статистика 3) Сортировка производится на месте, т.е. кроме исходного массива используется дополнительное пространство, не превышающее некоторой постоянной величины. а) Разработайте алгоритм, удовлетворяющий критериям 1 и 2. б) Разработайте алгоритм, удовлетворяющий критериям 1 и 3. в) Разработайте алгоритм, удовлетворяющий критериям 2 и 3.
г) Может ли какой-либо из представленных в частях а)-в) алгоритмов обеспечить поразрядную сортировку п записей с Ь-битовымн ключами за время О (Ьп)? Поясните, почему. д) Предположим, что и записей обладают ключами, значения которых находятся в интервале от 1 до 1с. Покажите, как можно модифицировать алгоритм сортировки подсчетом, чтобы обеспечить сортировку этих записей на месте в течение времени О (и+ к). В дополнение к входному массиву, можно использовать дополнительную память объемом О (1с). Устойчив ли этот алгоритм? (Указание: подумайте, как можно решить задачу для к = 3.) 8-3.
Сортировка элементов переменной длины а) Имеется массив целых чисел, причем различные элементы этого массива могут иметь разные количества цифр; однако общее количество цифр во всех числах равно и. Покажите, как выполнить сортировку этого массива за время О (и). б) Имеется массив строк, в котором различные строки могут иметь разную длину; однако общее количество символов во всех строках равно п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
