t=nmod4 – довжина залишку масиву після останньої повної четвірки елементів. При t=1 або t=2 останні t елементів утворюють упорядковану ділянку після попереднього кроку. При t=3 зливаються упорядкована пара B[n-1]B[n-2] та ділянка B[n] у ділянку довжиною t.
Кроки повторюються з подвоєнням довжин упорядкованих ділянок lp, поки lp < n.
Розглянемо сортування злиттям масиву довжини n=11. Упорядковані послідовності в ньому вказуються в дужках , а пари таких, що зливаються, відокремлені ";":
< ; ; ; ; ; >, lp=1
< ; ; >, lp=2
< ; >, lp=4
< >, lp=8
, lp=16, lp 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 = n : масив упорядковано на останньому кроці }
end
Очевидно, що після k-го кроку впорядковані ділянки мають довжину lp=2k. Якщо 2k=n, то масив упорядковано. Якщо 2k>n, але 2k-1 n/2, npp = 0, tl = n > lp,
і злиття ділянки довжиною lp та залишку довжиною n-lp дає впорядкований масив.
Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k a[c[ll]].y) or (tp.y > a[c[rr]].y)or
not( (tp.x>a[c[ll]].x)and(tp.x a[c[rr]].y)or
not( (tp.x>a[c[ll]].x)and(tp.x
Похожие работы
Тема: Сортування даних - пірамідальне сортування |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Курсовая работа (т)) |
Тема: Сортування даних - пірамідальне сортування |
Предмет/Тип: Другое (Курсовая работа (т)) |
Тема: Сортування матриці |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Курсовая работа (т)) |
Тема: Алгоритми сортування |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Практическое задание) |
Тема: Алгоритми сортування |
Предмет/Тип: Другое (Практическое задание) |
Интересная статья: Быстрое написание курсовой работы