|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[57] 9.3-2 Какие из следующих алгоритмов сортировки являются устойчивыми: сортировка вставками, сортировка слиянием, сортировка с помощью кучи, быстрая сортировка? Объясните, каким способом можно любой алгоритм сортировки превратить в устойчивый. Сколько при этом потребуется дополнительного времени и памяти? 9.3-3 Докажите по индукции, что алгоритм цифровой сортировки правилен. Где в вашем доказательстве используется устойчивость алгоритма сортировки цифр? 9.3-4 Объясните, как рассортировать га целых положительных чисел, не превосходящих га2, за время О (га). 9.3-5* Пусть мы сортируем перфокарты с помощью сортировочной машины, начиная со старшего разряда. Сколько раз придётся запустить машину (в худшем случае) для сортировки d-значных чисел? Какое максимальное количество стопок карт придётся одновременно хранить по ходу дела? 9.4. Сортировка вычерпыванием Алгоритм сортировки вычерпыванием (bucket sort) работает за линейное (среднее) время. Как и сортировка подсчётом, сортировка вычерпыванием годится не для любых исходных данных: говоря о линейном среднем времени, мы предполагаем, что на вход подаётся последовательность независимых случайных чисел, равномерно распределённых на промежутке [0; 1) (определение равномерного распределения дано в разд. 6.2). [Заметим, что этот алгоритм - детерминированный (не использует генератора случайных чисел); понятие случайности возникает лишь при анализе времени его работы.] Идея алгоритма состоит в том, что промежуток [0; 1) делится на га равных частей, после чего для чисел из каждой части выделяется свой ящик-черпак (bucket), и га подлежащих сортировке чисел раскладываются по этим ящикам. Поскольку числа равномерно распределены на отрезке [0;1), следует ожидать, что в каждом ящике их будет немного. Теперь отсортируем числа в каждом ящике по отдельности и пройдёмся по ящикам в порядке возрастания, выписывая попавшие в каждый из них числа также в порядке возрастания. Будем считать, что на вход подается га-элементный массив А, причем 0 А[г] < 1 для всех г. Используется также вспомогательный массив В[0 . .га - 1], состоящий из списков, соответствующих ящикам. Алгоритм использует операции со списками, которые опи- Рис. 9.4 Работа алгоритма Bucket-Sort, (а) На вход подан массив А[1. . 10]. (б) Массив списков В[0. . 9] после выполнения строки 5. Список с индексом г содержит числа, у которых первый знак после запятой есть г. Отсортированный массив получится, если последовательно выписать списки В[0],. . . , В[9]. 6 соединить списки В[0], В[1],..., В[п - 1] (в указанном порядке) На рис. 9.4 показана работа этого алгоритма на примере массива из 10 чисел. Чтобы показать, что алгоритм сортировки вычерпыванием правилен, рассмотрим два числа A[i] и A[j]. Если они попали в разные ящики, то меньшее из них попало в ящик с меньшим номером, и в выходной последовательности оно окажется раньше; если они попали в один ящик, то после сортировки содержимого ящика меньшее число будет также предшествовать большему. Проанализируем время работы алгоритма. Операции во всех строках, кроме пятой, требуют (общего) времени 0{п). Просмотр всех ящиков также занимает время 0{п). Таким образом, нам остаётся только оценить время сортировки вставками внутри ящиков. Пусть в ящик B[i] попало гц чисел {гц - случайная величина). Поскольку сортировка вставками работает за квадратичное время, математическое ожидание длительности сортировки чисел в ящике номер г есть 0(М[га2]), а математическое ожидание суммарного саны в разд. 11.2. 3do добавить A[i] к списку -B[LraWJ] 4for г +- 0 to п - 1 5do отсортировать список В\г\ (сорт! Глава 9 Сортировка за линейное время времени сортировки во всех ящиках есть п - 1/п-1 J]0(M[ra2])=0 £М[п?] (9.1) 8 = 0V 8 = 0 Найдём функцию распределения случайных величин гц. Поскольку числа распределены равномерно, а величины всех отрезков равны, вероятность того, что данное число попадет в ящик номер г, равна 1/га. Стало быть, мы находимся в ситуации примера из разд. 6.6.2 с шарами и урнами: у нас га шаров-чисел, га урн-ящиков, и вероятность попадания данного шара в данную урну равна р = 1/га. Поэтому числа гц распределены биномально: вероятность того, что гц = к, равна Скрк(1 - р)п~к, математическое ожидание равно М[гаг] = пр = 1, и дисперсия равна D[ra8] = гар(1- р) = 1 - 1/га. Из формулы (6.30) имеем: Подставляя эту оценку в (9.1), получаем, что математическое ожидание суммарного времени сортировки всех ящиков есть О (га), так что математическое ожидание времени работы алгоритма сортировки вычерпыванием в самом деле линейно зависит от количества чисел. Упражнения 9.4-1 Следуя образцу рис. 9.4, покажите, как работает алгоритм Bucket-Sort для массива А = (0.79,0.13,0.16,0.64,0.39, 0.20,0.89,0.53,0.71,0.42). 9.4-2 Каково время работы алгоритма сортировки вычерпыванием в худшем случае? Придумайте его простую модификацию, сохраняющую линейное среднее время работы и снижающую время работы в худшем случае до О (га lgra). 9.4-3* Дано га независимых случайных точек с координатами (жг;уг), равномерно распределённых в круге радиуса 1 с центром в начале координат (это означает, что вероятность найти точку в какой-то области пропорциональна площади этой области). Разработайте алгоритм, располагающий точки в порядке возрастания расстояния от центра и имеющий среднее время работы в (га). (Указание: воспользуйтесь сортировкой вычерпыванием, но позаботьтесь о том, чтобы площади ящиков были равны). M[ra2] = D[ra8] + M2[ra8] = 2 1 6(1). га 9.4-4* Пусть X - случайная величина. Ее функция распределения (probability distribution function) определяется формулой Р(х) = |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||