Цифровая распределяющая сортировка — КиберПедия 

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...

Цифровая распределяющая сортировка

2017-12-12 411
Цифровая распределяющая сортировка 0.00 из 5.00 0 оценок
Заказать работу

Применяется для упорядочивания 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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.01 с.