Пошук, сортування та поняття складності, Детальна інформація
Пошук, сортування та поняття складності
<1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11>, lp=16, lp\xF0B3 n.
Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив.
За дії означень (17.1) такий спосіб сортування описується процедурою Mrgsort:
procedure Mrgsort (var A : ArT; n : Indx);
var B : ArT; lp, npp, cpp, bpp, tl : integer;
begin
lp := 1;
while lp < n do
begin
B := A; { копіювання }
npp := n div (2*lp); { кількість пар ділянок }
tl := n mod (2*lp); { довжина залишку }
for cpp := 1 to npp do { cpp – номер пари }
begin
bpp := (cpp - 1)*2*lp + 1;
{ індекс першого елемента лівої ділянки пари}
mrg ( B, bpp, lp, lp, A );
end;
{ обробка залишку }
if tl > lp then
mrg ( B, n - tl + 1, lp, tl - lp, A );
{ за tl <= lp залишок був упорядкований }
{ на попередньому кроці }
lp := lp*2
end
{ lp >= n : масив упорядковано на останньому кроці }
end
Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1
lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp,
і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.
Як бачимо, нам знадобилося 4 кроки злиття для того, щоб одержати впорядований масив.
За дії означень (17.1) такий спосіб сортування описується процедурою Mrgsort:
procedure Mrgsort (var A : ArT; n : Indx);
var B : ArT; lp, npp, cpp, bpp, tl : integer;
begin
lp := 1;
while lp < n do
begin
B := A; { копіювання }
npp := n div (2*lp); { кількість пар ділянок }
tl := n mod (2*lp); { довжина залишку }
for cpp := 1 to npp do { cpp – номер пари }
begin
bpp := (cpp - 1)*2*lp + 1;
{ індекс першого елемента лівої ділянки пари}
mrg ( B, bpp, lp, lp, A );
end;
{ обробка залишку }
if tl > lp then
mrg ( B, n - tl + 1, lp, tl - lp, A );
{ за tl <= lp залишок був упорядкований }
{ на попередньому кроці }
lp := lp*2
end
{ lp >= n : масив упорядковано на останньому кроці }
end
Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1
lp = 2k-1 = 2k / 2 > n/2, npp = 0, tl = n > lp,
і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021