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

Применяется для упорядочивания 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.