Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2021-01-29 | 259 |
5.00
из
|
Заказать работу |
|
|
В случае простого слияния серии формируются из фиксированного числа элементов (2,4,8), при этом никак не учитывается, что данные могут быть уже частично отсортированы естественным образом.
Если сформировать серии таким образом, чтобы они образовывали естественным образом упорядоченные последовательности, то слияние будет выглядеть так:
X 1 7 3 6 4 9 8 5
Y 1 5 7 8 9 6 4 3
X 1 3 4 5 6 7 8 9
Рекурсивный алгоритм слияния
Алгоритм разбивает массив на две части, рекурсивно сортирует каждую половину, а затем сливает их в один отсортированный массив. Для хранения отсортированных половин используется вспомогательный массив y.
Чтобы не использовать «сторожевых» элементов можно применить следующий прием: первую половину копировать в прямом порядке, а вторую – в обратном.
Тогда каждый из подмассивов служит сторожем для другого – y[m+1] – максимум для всей правой части и сторож для левой части, y[m]- максимум для левой части и сторож для правой.
Procedure Merge(var x: vector; l, r: integer);
Var i, j, k, m: integer;
Y: vector;
Begin
If r-l>0 then
Begin
m:=(r+l) div 2;
Merge(x, l, m;)
Merge(x, m+1, r);
For i:=m downto l do y[i]:=x[i];
For j:=m+1 to r do y[r+m+1-j]:=x[j];
For k:=l to r do
If y[i]<y[j]
then
begin
x[k]:=y[i];
inc(i)
end
else
begin
x[k]:=y[j];
dec(j)
end
end
End;
Слияние списков
Основным недостатком алгоритмов слияния является использование дополнительной памяти размером в N элементов. В действительности, если добавить связи между исходными элементами, то все слияние можно легко произвести, манипулируя связями. Добавление N полей связи, как правило, выгоднее, чем хранение N дополнительных элементов. Кроме того, манипулируя связями, мы отказываемся от «дорогой» операции перемещения записей и экономим время сортировки.
|
Поэтому рассмотрим алгоритм слияния на связанных списках.
Procedure merge (L1, L2: Link; var L: Link);
Var p: link;
Begin
P:=z;
Repeat
if L1^.elem<=L2^.elem
then
begin
P^.next:=L1; P:=L1;
L1:=L1^.next
end
else
begin
P^.next:=L2; P:=L2;
L2:=L2^.next
end;
until P^.elem=Maxint;
L:=Z^.next;
z^.next:=z
End;
В программе списки L1, L2 имеют общий конечный узел («хвост») z, который указывает сам на себя. «Хвост» выполняет несколько полезных функций:
- Z^.elem содержит граничный сторожевой элемент ¥,
- Z^.next при слиянии используется в качестве указателя на начало объединенного списка,
- после слияния Z^.next снова устанавливается на себя.
Сравнение на равенство ключей (<=) делает сортировку устойчивой. Например, списки на рисунке в случае устойчивой сортировки дают в результате 1A, 2B, 2C, 2E, 2F, 3D, 4G.
1 | A | 2 | B | 2 | C | 3 | D | ¥ |
2 | E | 2 | F | 4 | G |
А в случае неустойчивой сортировки
1A, 2E, 2G, 2B, 2C, 3D, 4G.
В случае внутреннего слияния связанное распределение памяти имеет явные преимущества перед последовательным распределением: требуется меньше памяти и программа работает на 10-20% быстрее.
|
|
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!