Многофазная сортировка


     Этот тип сортировки относится к так называемым 'сортировкам слиянием'. Слиянием называется процесс объединения нескольких упорядоченных серий в одну.

Пример для 3-х серий, слияемых на 4-ю: 

   3 7 9      3 7 9        3 7 9          7 9             7 9 

 { 2 4 6  1 { 2 4 6  1 2 { 4 6    1 2 3 { 4 6   1 2 3 4 { 6  

   1 5 8      5 8          5 8            5 8             5 8

   

              7 9                7 9                 9

  1 2 3 4 5 { 6    1 2 3 4 5 6 { 8     1 2 3 5 6 7 { 8   1 2 3 4 5 6 7 8 9 {

              8
Таким образом, каждая операция слияния серий требует n пересылок элементов, где n - общее число элементов серий.

     Пусть у нас имеется N лент: N - 1 входная и одна пустая. Мы будем слиять элементы со входных лент на выходную, пока какая-либо из них не опустеет. Затем она станет входной.

Пример сортировки с шестью лентами, содержащими всего 65 серий:
Типf1f2 f3f4f5f6
16
8
4
2
1
0		 15
7
3
1
0
1		 14
6
2
0
1
0		 12
4
0
2
1
0		 8
0
4
2
1
0
8
4
2
1
0
     В каждый момент времени слияние происходит на пустую ленту с остальных, поэтому число требующихся проходов приблизительно равно log N n. В данном примере распределение начальных серий побрано искусственно. Для идеальной сортировки исходные числа серий должны быть суммами n - 1 , n - 2 , ... , 1 последовательных чисел Фибоначчи порядка n - 2.

     Число Фибоначчи порядка p определяются следующим образом:
fi+1(p) = fi(p) + fi-1(p) + ... + fi-p(p) для i >=p,
fp(p) = 1,
fi(p) = 0 для 0 <= i < p.
     Очевидно, обычные числа Фибоначчи имеют порядок 1.

     Поэтому предположим существование фиктивных серий, таких что сумма фиктивных с реальными дает идеальное число. Но как их распознавать при слиянии ?

     Рассмотрим этот вопрос поподробнее: ясно, что слияние участием фиктивной серии означает, что эта лента не участвует в слиянии. То есть слияние происходит с меньшего количества лент. Слияние фиктивных серий со всех n - 1 лент не предполагает в действительности никакого слияния. Это всего лишь запись фиктивной серии на выходную ленту. Поэтому мы заинтересованы в как можно более равномерном распределении фиктивных серий на n - 1 ленту.

Идеальное распределение серий на пяти лентах
уровень - l
 a1(l) a2(l) a3(l) a4(l) a5(l) сумма a i
0
1
2
3
4
5
1
1
2
4
8
16
0
1
2
4
8
15
0
1
2
4
7
14
0
1
2
3
6
12
0
1
1
2
4
8
1
5
9
17
33
65


     В первом приближении алгоритм распределения будет выглядить так:

     1. Пусть перед нами стоит цель - числа Фибоначчи порядки n - 2, уровня 1.

     2. Распределяем серии согласно поставленной цели.

     3. Если цель достигнута, вычисляем следующий уровень чисел Фибоначчи; разность между числами этого уровня и числами предыдущего уровня представляет собой новую цель распределения. Возвращаемся к шагу 2. Если цели нельзя достичь, потому что входные данные исчерпаны, распределение заканчивается.

     Сосредоточим внимание на шаге 2. Предположим, что, повышая уровень, мы записываем следующую цель с помощью разностей di для i = 1 , ... , n - 1, где di обозначает число серий, которые на данном шаге нужно отправить на ленту i. Теперь можно считать, что мы сразу помещаем di фиктивных серий на ленту i и рассматриваем последующее распределение как замену фиктивных серий действительными так, что при каждой замене di уменьшается на 1. Таким образом, di будет указывать число фиктивных серий на ленте i, когда входные данные будут исчерпаны.

     Мы будем использовать алгоритм горизонтального распределения: представим себе серии, сложенные в виде пирамиды.

Пример для n = 6, уровня 5 ( см таблицу ):

1
2
5
9
13
18
23
28
3
6
10
14
19
24
29
4
7
11
15
20
25
30

8
12
16
21
26
31



17
22
27
32


     Тeперь мы можем описать алгоритм в виде процедуры selecttape, которая вызывается каждый раз, когда переписана какая-либо серия и нужно выбрать ленту, с которой берется очередная серия. Мы предполагаем, что существует переменная j, обозначающая индекс текущей выходной ленты. Переменные ai и di обозначают числа идеального и фиктивного распределений для ленты i.

     Эти переменные мы будем инициализовать так:

a 1 = 1 , d i = 1 для i = 1 ... n - 1,
a n = 0 , d n = 0 ( фиктивные ),
j = 1, level = 1.
Вверх