Пошук, сортування та поняття складності у програмуванні, Детальна інформація
Пошук, сортування та поняття складності у програмуванні
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 дає впорядкований масив.
Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+\xF0EB log2n\xF0FB =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn).
Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+\xF0EB log2n\xF0FB ) та округлене відношення r двох останніх:
n n(n-1)/2 n(1+\xF0EB log2n\xF0FB ) r
10 45 40 1
100 4950 700 7
1000 499500 10000 50
10000 49995000 140000 350
Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+\xF0EB log2n\xF0FB ) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове!
Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою.
Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний:
procedure Mrgrec(var A, B : ArT; l, r : integer);
var m, k : integer;
begin
if l>=r then exit;
m:=(l+r) div 2;
Mrgrec(A, B, l, m); Mrgrec(A, B, m+1,r);
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 дає впорядкований масив.
Оцінимо складність наведеного алгоритму. При кожному виконанні тіла циклу while значення всіх елементів масиву копіюються в допоміжний масив і назад по одному разу, тобто виконується O(n) елементарних дій. Після останнього k-го кроку 2k<2n, тобто k<1+logn, і це означає, що тіло циклу while виконується 1+\xF0EB log2n\xF0FB =O(logn) разів. Отже, складність алгоритму оцінюється як O(nlogn).
Запишемо в таблицю значення виразів n, n(n-1)/2, n(1+\xF0EB log2n\xF0FB ) та округлене відношення r двох останніх:
n n(n-1)/2 n(1+\xF0EB log2n\xF0FB ) r
10 45 40 1
100 4950 700 7
1000 499500 10000 50
10000 49995000 140000 350
Як бачимо, кожне зростання n у 10 разів веде до зростання n(n-1)/2 та n(1+\xF0EB log2n\xF0FB ) приблизно в 100 й 14 разів відповідно, і за n=10000 сортування злиттям виконується в сотні разів скоріше, ніж бульбашкове!
Зауважимо, що в наведеному алгоритмі сортування злиттям копіювання масиву в допоміжний указано лише для того, щоб ідею алгоритму було простіше сприйняти. Цей алгоритм нескладно переробити так, щоб замість копіювання в додатковий масив відбувалося злиття в нього упорядкованих ділянок. Отже, на кроках з номерами 1, 3, 5, … має відбуватися злиття в допоміжний масив, а на кроках 2, 4, 6, … – злиття в протилежному напрямку. Переробка алгоритму залишається вправою.
Сортування злиттям можна задати рекурсивно: масив поділяється на дві приблизно рівні частини, які після сортування (тим самим способом – ось рекурсія!) зливаються. Коли ж довжина частини масиву зменшується до 1, відбувається просто повернення з рекурсії. Цей алгоритм уточнюється наступною процедурою Mrgrec. На відміну від процедури Merges, вона має два параметри-масиви (той, що сортується, та допоміжний), а також два числові параметри (початок і кінець частини масиву, яка сортується). Крім того, спочатку відбувається злиття ділянок основного масиву в допоміжний, а потім копіювання в основний:
procedure Mrgrec(var A, B : ArT; l, r : integer);
var m, k : integer;
begin
if l>=r then exit;
m:=(l+r) div 2;
Mrgrec(A, B, l, m); Mrgrec(A, B, m+1,r);
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021