Внешняя сортировка

Данный тип сортировки выполняется, если элементы не могут быть размещены в оперативной памяти. Основной метод сортировки файлов – слияние, т.е. объединение двух или более последовательностей в одну упорядоченность.

Приняты следующие понятия:

• фазы сортировки, операция однократной обработки последовательности элементов.

Выделяют две фазы алгоритма:

• разбиение;

• слияние.

Повторение двух указанных фаз образуют проход, представляющий собой подпроцесс сортировки.

Пусть A– исходная последовательность, тогда вышеуказанные понятия можно представить в виде схемы.

Метод простого слияния

1. Этап: Исходная последовательность Aразбивается на две отдельных последовательностейBиC.

2. Из последовательностей BиCвыполняется слияние элементов в упорядоченные пары элементов, формируя при этом частично упорядоченную последовательностьA.

3. Шаги 1и2повторяются, при этом на каждом проходе упорядоченные пары сливаются в четверки, четверки – в восьмерки и т.д. до тех пор, пока длина полученной упорядоченной последовательности не будет совпадать с исходной длиной последовательности.

A44 55 12 42 94 18 6 67

1. проход

фаза B: 44 55 12 42

разбиения C: 94 18 6 67

фаза слияния : 44 94 18 55 6 12 42 67

2. проход B: 44 94 18 55

C: 6 12 42 67

: 6 12 44 94 18 42 55 67

длина = 4 «четверки»

3 проход B: 6 12 44 94

C: 18 42 55 67

: 6 12 18 42 44 55 67 94

Метод естественного слияния

Любая последовательность включает фрагменты частично упорядоченных последовательностей. Данный метод производного слияния упорядоченных последовательностей. А сама упорядоченная последовательность называется серией.

a_i. . .a_j– это упорядоченная подпоследовательность, еслиki. . .j,

a[k] <= a[k+1] a[i] < a[i – 1] и a[j] > a[j + 1].

Пример:

17 31 5 59 13 41 43 67 11 23 29 47 3 7 71 5

1 проход: B: 1713 41 43 3 7

C: 5 11 23 29 5

: 5 17 31 11 13 23 29 41 43 47 3 5 6 71

2 проход: B: 5 17 313 5 7 71

C: 11 13 23 29 41 43 47

: 5 11 13 17 23 29 31 41 43 47 69 3 5 7 71

3 проход: B= . . .

C= .. .

: 3 5 5 7 11 13 23 . . . 71

Метод сбалансированного многопутевого слияния

Данный метод фактически исключает фазу разбиения, используя только фазу слияния. При этом в качестве выходных последовательностей, на которые переписываются элементы. Максимальное количество выходных файлов равно количеству серий последовательности. Количество последовательностей должно быть кратно двум.

Основные этапы:

1. Выбираются количество последовательностей.

2. Исходная последовательность разбивается на половину выходных последовательностей.

3. С выходных последовательностей, которые в данный момент фиксируется как входные; происходит слияние с соответствующей серией и их переписывание на вторую половину выходных последовательностей.

4. Далее выполняется повторяющийся процесс слияния серий из полученных последовательностей в свободную половину. Процесс заканчивается, когда останется одна последовательность, длина которой равна исходной.

Пример. Сортировка с использованием 6-ти выходных последовательностей.

17 1323 2911314 6141–2

выходные 1: 17 1141–4входные

последовательности 2: 13 31последовательности

3: 23 29 4 61–2

4: 13 17 19 23 29 33 –4 выходные

5: 4 11 31 45 59 61 80 последовательности

6: –2 5 41 43

входные 1: –2 4 5 11 13 17 19 . . . 61 80

2: –4

3: –

4: –4 –2 . . . 80

5:

6: