История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2017-12-12 | 428 |
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.
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!