Псевдокод операций используемых надd-кучей и некоторые оценки сложности.
Diving(i)
{
j1=i;
j2=MinChild(i);
while ( !IsLeaf(j1) && (Key[j2] <= Key[j1] ) )
{
Swap(j1,j2);
j1=j2;
j2=MinChild(j1);
}
}
MinChild(i){
L=LeftChild(i),R=RightChild(i);
if (L == -1)
return i; //если нет потомков
min_key=Key[L];
minchild=L;
for(j=L+1; j<R+1; j++)
if( Key[j] <= min_key)
{
minchild=j;
min_key=Key[j];
}
return minchild;
}
IsLeaf(i){
if( i*D+1 >=N )
returntrue; ; // d-куча с d=D и числом элементов =N
return false;
}
LeftChild(i){
if (IsLeaf(i))
return -1;
return 1+(D*i);
}
RightChild(i){
if (IsLeaf(i))
return -1;
else if( i*D+D < count-1)
return i*D+D;
return count-1;
}
Swap(a,b){ Key[a] Key[b]; }
DeleteMin{
if(count==0)returnKey[0];// возвращается корень для сортировки
Swap(0, (N-1) );
N--;
Diving(0);
return Key[0];
}
MakeHeap(){
for(i≤N-1;i≥0;i--)
Diving(i);
}
SortHeap()
{
MakeHeap();
for(i=0;i≤n-1;i++)
{
W=DeleteMin();
Sort[i]=w;
}
}
Алгоритм сортировкиk-слиянием.
Ее рекурсивная реализация состоит в разбиении массива на k приблизительно одинаковых частей, их сортировкой с последующим объединением отсортированных фрагментов. Для этого используются две процедуры: SORT_MERGE(a,i,j,k) и MERGE(a,i,m,j), первая из которых сортирует по неубыванию отрезок a[i…j] заданного массива a[1…n], вторая сливает уже отсортированные массивы a[i…m] и a[m+1…j]. Вызов первой процедуры с параметрами i=1 и j=n сортирует весь массив a.
procedure SORT_MERGE(var a;i,j,k);
begin
if(j-i+1
)thenсортировка отрезкаa[i..j]
каким-нибудь простым способом
(например, пузырьковой сортировкой)
else begin
step:=(j-i+1) div k;
for numb:= 0 to k-1 do begin
if (numb<k-1) then SORT_MERGE(a,i+step*numb,i+step*(numb+1)-1,k)
else SORT_MERGE(a,i+(k-1)*step,j,k);
end;
for numb:= 0 to k-2 do begin
if (numb<k-2) then MERGE(a,i,i+step*(numb+1)-1, i+step*(numb+2)-1)
else MERGE(a,i,i+(k-1)*step-1,j);
end;
end;
end;
procedure MERGE(var a;i,m,j);
begin
1. Создание массива bразмеромj-i+1, инициализация переменныхi1:=i,i2:=m+1;
2. В цикле, пока i1+i2<j+m+2, выполняются следующие операции:
2.1. Если (i1
m
и i2<j+1
и a[i1]
a[i2])
или (i2=j+1),
то b[i1+i2-i-m]:=a[i1]
и i1:=i1+1;
2.2. Во всех остальных случаях b[i1+i2-i-m]:=a[i2] иi2:=i2+1;
3. Скопировать содержимое массива bв массивa[i…j].
end;
Алгоритм сортировки вставками.
В сортировке k-слиянием должен использоваться какой-нибудь простой способ сортировки. В моей работе используется алгоритм сортировки вставками.
В данном алгоритме мы рассматриваем массив на i-ом шаге. Массив к этому моменту разделен на две части: отсортированную ( от a[0] до a[i] ) и неупорядоченную ( начиная с a[i+1] до a[n] ).
На каждом следующем (i+1)-ом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива.
Поиск подходящего места для очередного элемента (т.е. a[i+1] ) осуществляется путем последовательных сравнений с элементами, стоящими перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется.