Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 48
Текст из файла (страница 48)
Оцените количество дополнительного времени и объем памяти, необходимые для реализации этой схемы. Докажите методом математической индукции корректность работы поразрядной сортировки. Где в доказательстве используется предположение об устойчивости промежуточной сортировки? 8.3.4 Покажите, как выполнить сортировку и чисел, принадлежащих интервалу от О до пз — 1 за время 0(п). 8.3.5 * Определите точное количество проходов, которые понадобятся для сортировки д-значных десятичных чисел в наихудшем случае, если используется сортировка перфокарт, начинающаяся со старшей цифры.
За каким количеством стопок перфокарт нужно будет следить оператору в наихудшем случае? Часть РЕ Сортировка и порядковая статистика 8.4. Карманная сортировка В случае карманной сортировки (Ьпс(се1 зои) предполагается, что входные данные подчиняются равномерному закону распределения; время работы в среднем случае при этом оказывается равным 0(и). Карманная сортировка, как и сортировка подсчетом, работает быстрее, чем алгоритмы сортировки сравнением. Это происходит благодаря определенным предположениям о входных данных. Если при сортировке методом подсчета предполагается, что входные данные состоят из целых чисел, принадлежащих небольшому интервалу, то при карманной сортировке предполагается, что входные числа генерируются случайным процессом и равномерно распределены в интервале [0,1) (определение равномерного распределения можно найти в разделе В.2).
Карманная сортировка разбивает интервал [О, 1) на и одинаковых интервалов, или карманов (Ьис(се1з), а затем распределяет по этим карманам и входных чисел. Поскольку последние равномерно распределены в интервале [0,1), мы предполагаем, что в каждый из карманов попадет не очень много элементов, Чтобы получить выходную последовательность, нужно просто выполнить сортировку чисел в каждом кармане, а затем последовательно перечислить элементы каждого кармана.
При составлении кода карманной сортировки предполагается, что на вход подается массив А, состоящий из и элементов, и что величина каждого принадлежащего массиву элемента А[в] удовлетворяет неравенству 0 < А[1] < 1. Для работы нам понадобится вспомогательный массив связанных списков (карманов) В[0 ..
и — 1]; предполагается, что в нашем распоряжении имеется механизм поддержки таких списков. (Реализация основных операций при работе со связанным списком описана в разделе 10.2.) ВОскет-БОкт(А) 1 и = А.1еидй 2 Пусть В[0 ., и — 1] — новый массив 3 хогг'=Отои — 1 4 Сделать В[1] пустым списком 5 хогг' = 1 Гоп б Вставить А[(] в список В[[иА[з]]] 7 Гога'=Огои — 1 8 Отсортировать список В[в] сортировкой вставкой 9 Соединить списки В[0], В[1],..., В[и — 1] в указанном порядке На рис.
8.4 показана работа карманной сортировки с входным массивом из десяти чисел. Чтобы понять, как работает этот алгоритм, рассмотрим два элемента — А[1] и А[1]. Без потери общности можно предположить, что А[1] < А[7]. Поскольку [иА[г]] < [иА[1]], элемент А[1] помещается либо в тот же карман, что и элемент А[7], либо в карман с меньшим индексом. В первом случае элементы А[1] Гласа Д Сортировке за лииейиае ерема 451 Рис.
8.4. Работа процедуры Воскят-Бокт дла и = 10. (а) Входной массив А[1 .. 10]. (9) Массив В[0 .. 9] отсортированных списков (карманов) после строки а алгоритма. В кармане з хранатсв знииниа ю полуоткрыто»о интервала [(/10, (4+ 1)/10). Отсортированные выходные данные представлыат собой изнкатеныпно списков В[0],В[1],..., В[9] в указанном порядке. и А[)] располагаются в нужном порядке благодаря циклу вог в строках 7 и 8. Если же эти элементы попадут в разные карманы, то они разместятся в правильном порядке после выполнения строки 9.
Таким образом, карманная сортировка работает корректно. Чтобы проанализировать время работы адгоритма, заметим, что в наихудшем случае для выполнения всех его строк, кроме строки 8, требуется время 0[п). Остается просуммировать полное время, которое потребуется для п вызовов алгоритма сортировки вставкой (строка 8). Чтобы оценить стоимость этих вызовов, введем случайную величину и,, обозначающую колнчеспю элементов, попавших в карман В[3[.
Поскольку время работы апгорнтма сортировки вставкой является квадратичной функцией от количества входных элементов (см. раздел 2.2), время работы алгоритма карманной сортировки равно п — 1 Т[п) = тт[п) + ~~» О[п4) . Теперь проанализируем время работы карманной сортировки в среднем случае, вычисляя математическое ожидание времени работы, где усреднение производится по входному распределению. Применяя операцию математического ожи- (,79[ Ч) 7~ рот» 3 (Эй 4,'Дб[ 5 ',72,' б»94,' в»((т ю [бй[ (41 В, 1.л а»,;(» '.Ц ь,!;фъ,',:", „»'1"»* .'.» :=".
- ~хэ)»[' —:- ~'.~~"~Г.-~Ч6'.~': 3:-:,+ 4.39[,у": 4 [л(» б,.'::4» - -з-»да(лл ) . „'-'-",--;.т";:--..--:„-а»:, -> в [л»] [:Л в»,»'-';- изр41'~;":.,~ (б) Часть П. Сортировка и порядковая статистика гз2 дания к обеим частям н используя ее линейность, получаем и-1 Е [Т(п)] = Е ко(п) + ~~ 0(пз) г=о = 9(п) + ~ ~Е [0(пд)] (из линейности математического ожидания) =о и — 1 = 9(п) + ~ 0 (Е [п~] ) (согласно (В.22)) . (8.1) г=с Мы утверждаем, что (8.2) К, = 1(АЫ попадает в карман 1) Следовательно, п,=~~г Х, 1=1 Чтобы вычислить величину Е ]пи], раскроем квадрат и перегруппируем слагае- мые: Е [пк] = Е ~~г Хз Е [Хзу] + ~~ ~~г Е [Хз.Хгь], (8.3) \<1<п 1<1 <п Ьфз где последнее равенство следует из линейности математического ожидания.
Отдельно вычислим обе суммы. Индикаторная случайная величина Х; равна 1 с ве- для 1 = О, 1,..., п — 1. Не удивительно, что каждому 1-му карману соответствует одна и та же величина Е [п~], поскольку все злементы входного массива могут попасть в любой карман с равной вероятностью.
Чтобы доказать уравнение (8.2), определим для каждого 1 = О, 1,..., и — 1 и 1 = 1, 2,..., и индикаторную случайную величину Глава В. Сортировка за лиит1иое время 233 роятностью 1/и и 0 — в противном случае, поэтому получаем Е(Хг~ =1' -'+О' (1 — -') 1 Прн и ф 3 величины Х; и Хвь независимы, а следовательно, Е[Х11Хеь) = Е(Х1 Д Е(Х1ь) 1 1 п п 1 Подставив эти величины в уравнение (8.3), получим Е [п~~ = ~~~ — + г 1 1=1 1<1<о1<ь<о Ьфэ 1 1 = п — + и(и — 1) и пг и — 1 =1+ и 1 =2 — —, п что доказывает уравнение (8.2). Используя это ожидаемое значение в уравнении (8.1), приходим к выводу, что время работы алгоритма карманной сортировки в среднем случае равно 19(п) + и 0(2 — 1/и) = 0(п).
Такая зависимость может наблюдаться даже в том случае, когда входные элементы не подчиняются закону равномерного распределения. Если входные элементы обладают тем свойством, что сумма возведенных в квадрат размеров карманов линейно зависит от количества входных элементов, уравнение (8.1) утверждает, что карманная сортировка этих данных выполняется в течение времени, линейно зависящего от количества данных.
Упражнении 8.4.1 Используя рис.8.4 в качестве образца, проиллюстрнруйте работу алгоритма В13сккт-Вокт иад массивом А = (.79,.13,.16,.64,.39,.29,.89,.53,.71,.42). 8.4.г Поясните, почему время работы карманной сортировки в наихудшем случае составляет 19(пг).
Какое простое изменение следует внести в этот алгоритм, чтобы, Часть СЬ Сортировка к корядковая статистика сохранив линейное время работы в среднем случае, добиться в наихудшем случае времени работы 0(и 1к и)? 8.4.3 Пусть Х вЂ” случайная величина, равная количеству выпадений орла при двух бросках правильной монеты. Чему равно Е [Хз[? Ез [Х[? 8.4.4 * Даны и точек в единичном круге, р, = (х;, у,), такие, что О < хз + у~ < 1 для 1 = 1, 2,..., и.
Предположим, что эти точки равномерно распределены, т.е. вероятность найти точку в любой области круга пропорциональна плошади этой области. Разработайте алгоритм с временем работы 9(п) в среднем случае для сортировки и точек по их расстояниям б, = ~1?х~+ уз от центра. (Указание: спроектируйте размеры карманов в Вцскет-Яокт, которые отражали бы равномерность распределения точек в единичном круге.) 8.4.5 * Функция распределения вероятности Р(х) случайной величины Х определяется как Р(х) = Рг (Х < х). Предположим, что у нас есть список из п случайных величин Хы Хз,..., Х„с непрерывной функцией распределения вероятности Р, вычислимой за время 0(1). Разработайте алгоритм, сортируюший этот список за линейное время в среднем случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
