- •Сортировка слиянием (метод простого двухпутевого слияния)
- •Таблица на каждом шаге сортировки- совокупность равных упорядоченных групп, которые попарно сливаются, образуя
- •Алгоритм сортировки таблицы методом простого двухпутевого слияния
- •Вспомогательный алгоритм
- •Procedure sl(T, i1,k1,i2,k2);
- •Локальные переменные алгоритма сортировки:
- •Алгоритмы поиска в таблицах
- •Для неупорядоченных таблиц- метод линейного поиска (последовательный перебор всех записей)
- •Для упорядоченных таблиц- метод дихотомического
- •Например, ищем 32:
- •Алгоритм дихотомического поиска
- •Локальные переменные:
- •Динамические структуры данных
- •Распределение памяти при выполнении программы:
- •Ограничения на использование статической памяти:
- •Доступ к динамической памяти
Сортировка слиянием (метод простого двухпутевого слияния)
1
Таблица на каждом шаге сортировки- совокупность равных упорядоченных групп, которые попарно сливаются, образуя новые упорядоченные группы.
2
TAB
i1
23
68
i2
17
19
Исходная
таблица
|
|
|
|
|
|
|
TAB |
|
|
|
|
|
|
|
|
|
|
|
PS |
|
|
|
... |
|
|
|
|
|
|
|
|
|
|
|
|
|
i1 |
|
|
|
|
|
17 |
|
|
||
l1 |
|
|
|
|
|||
|
|
|
|
|
|||
|
|
|
|
|
|
|
17 |
|
|
|
19 |
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
|
|
|
|
23 |
|
|
|
23 |
|
|
|
|
|
|
68 |
|
|
|
|
|
|
|
|
|
l2 |
68 |
|
|
|
|
||
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
... |
|
|
|
|
|
|
|
|
Поле Упорядоченная слияния таблица
Алгоритм сортировки таблицы методом простого двухпутевого слияния
Параметры:
T – сортируемая таблица;
n – число записей в таблице.
4
Вспомогательный алгоритм
Слияние двух упорядоченных подтаблиц в одну, тоже упорядоченную
Параметры:
T-таблица |
|
i1, i2-индексы начала сливаемых |
|
подтаблиц |
|
k1, k2-длины сливаемых подтаблиц |
|
Промежуточная таблица: |
|
PS- поле слияния |
5 |
T: |
i1 |
|
|
|
i2 |
|
|
|
|
… |
2 |
6 |
9 |
18 |
3 |
7 |
19 |
22 |
… |
|
|
|
k1 |
|
|
|
k2 |
|
|
PS:
… 2 3 6 7 9 18 19 22 …
k1+k2
Procedure sl(T, i1,k1,i2,k2); |
|
|
begin |
j2:=i2; j:=i1; |
|
j1:=i1; |
|
|
while(j1<i1+k1) and (j2<i2+k2) |
||
begin |
|
|
if t[j1].key<t[j2].key then Сравниваем |
||
begin |
очередные |
|
ps[j]:=t[j1]; j1:=j1+1; |
элементы |
|
end |
else |
групп и |
begin |
заполняем |
|
ps[j]:=t[j2]; j2:=j2+1 |
поле слияния |
end; j:=j+1;
end;
while j1<i1+k1 do
begin ps[j]:=t[j1]; j:=j+1; j1:=j1+1
End;
Если вторая группа закончилась раньше
while j2<i2+k2 do begin
ps[j]:=t[j2];
j:=j+1;
j2:=j2+1 End;
For j:=i1 to i2+k2-1 do
t[j]:=ps[j];
Если первая группа закончилась раньше
i1 |
12 |
|
14 |
|
22 |
|
30 |
i2 |
8 |
|
15 |
|
17 |
|
18 |
|
j1 |
|
j1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
12 |
12 |
j1 |
12 |
|
|
|
12 |
|
|
|
12 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
14 |
14 |
|
|
|
14 |
|
|
|
14 |
|
|
|
|||
|
|
|
|
14 |
|
|
|
|
|
|
|
|
|
|
j1 |
||||||||
|
|
|
|
|
|
|
|
22 |
|
|
|
22 |
|
j1 |
22 |
j1 |
22 |
|
|||||
|
|
|
|
22 |
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
30 |
|
|
|
30 |
|
|
|
30 |
|
|
|
30 |
|
|
|
30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j2 |
|
8 |
|
|
|
8 |
|
|
|
8 |
|
|
|
8 |
|
|
|
8 |
|
|
|
||
|
|
|
|
|
15 |
|
|
|
15 |
|
|
|
15 |
|
|
|
15 |
|
|
|
|||
|
15 |
j2 |
|
j2 |
|
j2 |
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
17 |
|
|
|
17 |
|
17 |
|
|
|
17 |
|
|
|
||
|
|
|
|
17 |
|
|
|
|
|
|
j2 |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
18 |
|
|
|
18 |
|
|
|
18 |
|
|
|
18 |
|
|
|
|
|
|
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
j2 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
12 |
|
14 |
|
15 |
|
17 |
|
18 |
||||||||||||
|
|
|
|
|
|
|
|
П О Л Е С Л И Я Н И Я |
|
|
|
|