1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку. Перевірка виконання домашнього завдання.
2. Актуалізація опорних знань
- Що називають сортуванням масиву?
- Які ви знаєте методи сортування масивів?
- По яким параметрам проводиться оцінка алгоритмів?
Алгоритм сортування злиттям було розроблено Джоном фон Нейманом у 1945 році. В основі цього методу лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку.
Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах, і вказує, якому з них потрібно ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє доти, поки одна з колон не вичерпається. Тоді решту іншої колони долучають до нової.
Алгоритм побудовано за принципом «розділяй та володарюй». Масив поділяють на однакові (або практично однакові) за довжиною частини, кожну з яких впорядковують окремо. Після цього впорядковані частини «зливають» — див. ілюстрацію, запозичену з сайту Вікіпедії.
Детальніший опис при впорядкуванні за зростанням має такий вигляд:
Масив поділяють на однакові (або практично однакові) за довжиною частини. Кожну з отриманих частин знову поділяють навпіл до тих пір, поки не отримають одноелементні масиви.
Далі виконують злиття отриманих сусідніх частин (підмасивів):
з двох 1-елементних частин утворюють одну 2-елементну частину, розташувавши спочатку менший елемент, а потім більший;
- з двох 2-елементних частин утворюють одну 4-елементну частину, порівнюючи елементи двох масивів, починаючи з початку. Менший з них записують у новостворений масив. Потім у масиві, елемент якого виявився меншим, переходять до наступного елемента. Далі продовжують порівнювати перші з незаписаних у новий масив елементів і формувати таким чином новий масив. У випадку, якщо одну з частин буде вичерпано, елементи іншої дописують у новостворений масив у тому самому порядку; …
В кінці операції злиття елементи новоутвореного масиву перезаписують у початковий масив.
Розіб'ємо задачу впорядкування масиву A із n елементів на простіші підзадачі, кожну з яких розв'яжемо окремо.
Нехай k — натуральне число. Розіб'ємо масив A на частини довжини k, вказавши діапазони зміни індексу (номера) елемента: 1..k, (k + 1)..2k і т.д. Назвемо масив k-впорядкованим, якщо кожну з цих частин довжини k впорядковано.
Будь-який масив 1-впорядкований. Якщо масив k-впорядкований, і n ≤ k, то він впорядкований.
Загальна схема алгоритму має такий вигляд:
while k < n do
begin
{перетворити k-впорядкований масив у 2k-впорядкований};
k:=k*2;
end;
Розглянемо процедуру перетворення k-впорядкованого масиву у 2k-впорядкований. Згрупуємо всі підмасиви довжиною k у пари підмасивів. Тепер пару впорядкованих підмасивів зіллємо в один упорядкований підмасив. Виконавши це зі всіма парами, отримаємо 2k-впорядкований масив. Позначимо через:
t — кількість елементів масиву, що вже перетворено з k-впорядкованого у 2k-впорядкований;
q = t + k — номер останнього елемента першої з пари частин, які будуть «зливати»;
r = t + 2k — номер останнього елемента другої з пари частин, які будуть «зливати».
Інакше кажучи, ми будемо «зливати» дві частини (підмасиви) по k елементів з індексами (t + 1)..q і (q + 1)..r.
t:=0;
while t + k <= n do
begin
q:=t+k;
if t+2*k<n then r:=t+2*k
else r:=n;
… {злити підмасиви з індексами t+1..q і q+1..r}
t:=r;
end;
Злиття вимагає використання допоміжного масиву В для запису результатів злиття.
Запровадимо такі позначення:
p0 і q0 — номери останніх елементів частин масиву, що були злиті;
s0 — номер елемента масиву В, якому останнім було змінено значення.
На кожному кроці злиття виконують одну з двох послідовностей вказівок:
- або B[s0+1]:=A[p0+1]; Inc(p0); Inc(s0);
- або B[s0+1]:=A[q0+1]; Inc(q0); Inc(s0);
p0 < q — першу частину ще не вичерпано;
(q0 = r) ∨ ((q0 < r) ∧ (A[p0 + 1] ≤ A[q0 + 1])) — другу частину вичерпано (q0 = r) або її не вичерпано (q0 < r), але черговий елемент у ній не менший від чергового елемента першої частини.
Інакше виконують другу послідовність вказівок. Якщо обидві частини не вичерпано, і перші не враховані елементи в них збігаються, тобто можна брати довільний з них, то буде обрано елемент з першої частини (з меншими індексами). Остаточно маємо:
p0:=t;
q0:=q;
s0:=t;
while (p0<>q) or (q0<>r) do
if (p0<q) and ((q0=r) or ((q0<r) and (A[p0+1]<=A[q0+1])))
then begin B[s0+1]:=A[p0+1]; Inc(p0); Inc(s0) end
else begin B[s0+1]:=A[q0+1]; Inc(q0); Inc(s0) end;
Недоліком впорядкування злиттям є використання додаткової пам'яті для збереження масиву такого самого розміру, як і той, що впорядковують. Але при роботі з файлами або списками, доступ до яких здійснюють лише послідовно, це дуже зручний метод. Перевагою алгоритму також є його стійкість (він не міняє місцями однакові за значенням елементи) та прийнятна ефективність O(n log n).
4. Інструктаж з ТБ
5. Закріплення вивченого матеріалу
Завдання. Використовуючи фрагменти коду, подані у викладі нового матеріалу, написати програму, яка:
- зчитає з файлу input.txt кількість елементів лінійного масиву та їхні значення;
- впорядкує лінійний масив методом злиття;
- запише у файл output.txt елементи масиву у порядку неспадання.
Програму записати з назвою Ваше прізвище у теку, вказану вчителем.
6. Підбиття підсумків уроку
Виставлення оцінок.
7. Домашнє завдання
Порівняти створену у класі програму з демонстраційними розв'язанням.
Ознайомитися з використанням методу злиття у розв'язуванні задач учнівських олімпіад з інформатики — див. опис розв'язання задачі 3 «Істотні інверсії» ІІІ етапу за матеріалами журнальної публікації.
Текст упорядкувала Анікіна Лариса Павлівна, вчитель гімназії № 143 Оболонського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 24.11.2014 по 12.12.2014.