Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2017-12-12 | 411 |
5.00
из
|
Заказать работу |
|
|
Применяется для упорядочивания n-ричных чисел.
Идея: просматривая записи последовательно, распределяем их на группы с одинаковой последней цифрой. После этого группы снова объединяются в один массив в порядке возрастания последних цифр. Затем это же проделывается с получившимся массивом для второй с конца цифры, и так столько раз, какова разрядность чисел. При этом очередной проход не нарушает упорядоченности по уже обработанным разрядам.
Данный метод более сложный, но в месте с тем более экономичный.
На рис. 3.11 показано, как осуществляется такая сортировка для трехзначных чисел.
Рис. 3.11. Пример алгоритма цифровой распределяющей сортировки
Метод предсортировки и слияния
Метод максимумов
Рис. 3.12 Блок-схемы алгоритмов
Сортировка последовательных файлов
Простое слияние
Слияние означает объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Слияние — намного более простая операция, чем сортировка; она используется в качестве вспомогательной в более сложном процессе последовательной сортировки.
Метод сортировки простым слиянием состоит в следующем:
1. Последовательность а разбивается на две половины b и с.
2. Последовательности b и с сливаются при помощи объединения отдельных элементов в упорядоченные пары.
3. Полученной последовательности присваивается имя а, и повторяются шаги 1 и 2; упорядоченные пары сливаются в упорядоченные четверки.
|
4. Предыдущие шаги повторяются: четверки сливаются в восьмерки, и весь процесс продолжается до тех пор, пока не будет упорядочена вся последовательность, ведь длины сливаемых последовательностей каждый раз удваиваются.
В качестве примера рассмотрим последовательность:
44 55 12 42 94 18 06 67
На первом шаге разбиение дает последовательности:
44 55 12 42
94 18 06 67
Слияние отдельных компонент (которые являются упорядоченными последовательностями длины 1) в упорядоченные пары дает:
44 94 / 18 55 / 06 12 / 42 67
Новое разбиение пополам и слияние упорядоченных пар дают:
06 12 44 94 / 18 42 55 67
Третье разбиение и слияние приводят к нужному результату:
06 12 18 42 44 55 67 94
Естественное слияние
Исходная последовательность элементов задана в виде файла с, который в конце работы должен содержать результат сортировки. Каждый проход состоит из фазы распределения, которая распределяет упорядоченные подпоследовательности поровну из с в а и b, и фазы слияния, которая сливает упорядоченные подпоследовательности из а и b в с. Этот процесс показан на рис. 3.13.
Рис. 3.13. Фазы сортировки и проходы сортировки
В качестве примера на рис. 3.14 показан файл с в исходном состоянии (строка 1) и после каждого прохода (строки 2-4).
’ 5 | ’13 | ’11 | ’ 3 | ’2 | ’37 | ||||||||||||||
’11 | ’ 2 | ’37 | |||||||||||||||||
’ 2 | |||||||||||||||||||
Рис. 14. Пример сортировки естественным слиянием
В естественном слиянии участвуют 20 чисел. Требуются только три прохода. Сортировка заканчивается, как только число упорядоченных подпоследовательностей в с будет равно 1.
|
|
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!