const maxA=1000;
type TArray=array[0..maxA]of real;
procedure merge(var A:TArray;p,q,r:integer);
var n1,n2,i,j,k:integer;
B:TArray;
begin
n1:=q-p+1;
n2:=r-q;
for i:=p to r do
B[i-p+1]:=A[i];
i:=1;
j:=n1+1;
k:=p;
while((i<=n1)and(j<=n1+n2)) do
begin
if(B[i]<=B[j]) then
begin
A[k]:=B[i];
i:=i+1;
end
else
begin
A[k]:=B[j];
j:=j+1;
end;
k:=k+1;
end;
while(i<=n1) do
begin
A[k]:=B[i];
i:=i+1;
k:=k+1;
end;
while(j<=n1+n2) do
begin
A[k]:=B[j];
j:=j+1;
k:=k+1;
end;
end;
procedure mergeSort(var A:TArray;size:integer)
var curr,left,mid,right:integer;
begin
curr:=1;
while(curr<=size-1) do
begin
left:=0;
while(left<size-1) do
begin
mid:=left+curr-1;
if(left+2*curr-1<size-1) then
right:=left+2*curr-1
else right:=size-1;
merge(A,left,mid,right);
left:=left+2*curr;
end;
curr:=curr*2;
end;
end;
Problem w tym że procedura sortująca napisana jest dla tablic indeksowanych od zera
a procedura scalająca napisana jest dla tablic indeksowanych od jedynki
Przypuśćmy że chcemy aby tablica była indeksowana od jedynki
Jak przesunąć indeksy w procedurze sortującej
Jaka jest złożoność procedury sortującej
Mam wątpliwości czy tak napisana procedura sortująca ma nadal złożoność O(nlogn)
Skoro koniecznie chcecie C to przepiszę interesującą mnie procedurę na C
void mergeSort(double* A,int size)
{
int curr,left,mid,right;
curr=1;
while(curr<=size-1)
{
left=0;
while(left<size-1)
{
mid=left+curr-1;
if(left+2*curr-1<size-1)
right=left+2*curr-1;
else right=size-1;
merge(A,left,mid,right);
left=left+2*curr;
}
curr=curr*2;
}
}