Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Data_Structure / лекц04.ppt
Скачиваний:
44
Добавлен:
03.03.2016
Размер:
97.79 Кб
Скачать

Сортировка слиянием (метод простого двухпутевого слияния)

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

 

 

 

 

 

 

 

 

П О Л Е С Л И Я Н И Я

 

 

 

 

Соседние файлы в папке Data_Structure