Розробка уроку — практичної роботи

Тема: впорядкування злиттям.

Мета: навчитися складати програму для впорядкування лінійного масиву методом злиття у середовищі Free Pascal. Після виконання роботи учень:

Обладнання: ПК з встановленими ОС і середовищем програмування Free Pascal, (дана) інструкція.

Структура уроку

  1. Організаційний момент.
  2. Актуалізація опорних знань.
  3. Вивчення нового матеріалу.
  4. Інструктаж з ТБ.
  5. Вироблення практичних навичок.
  6. Підбиття підсумків уроку.
  7. Домашнє завдання.
Хід уроку

1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку. Перевірка виконання домашнього завдання.

2. Актуалізація опорних знань
  1. Що називають сортуванням масиву?
  2. Які ви знаєте методи сортування масивів?
  3. По яким параметрам проводиться оцінка алгоритмів?
3. Вивчення нового матеріалу

Алгоритм сортування злиттям було розроблено Джоном фон Нейманом у 1945 році. В основі цього методу лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку.

Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах, і вказує, якому з них потрібно ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє доти, поки одна з колон не вичерпається. Тоді решту іншої колони долучають до нової.

Алгоритм побудовано за принципом «розділяй та володарюй». Масив поділяють на однакові (або практично однакові) за довжиною частини, кожну з яких впорядковують окремо. Після цього впорядковані частини «зливають» — див. ілюстрацію, запозичену з сайту Вікіпедії.

Детальніший опис при впорядкуванні за зростанням має такий вигляд:

  1. Масив поділяють на однакові (або практично однакові) за довжиною частини. Кожну з отриманих частин знову поділяють навпіл до тих пір, поки не отримають одноелементні масиви.

  2. Далі виконують злиття отриманих сусідніх частин (підмасивів):

    • з двох 1-елементних частин утворюють одну 2-елементну частину, розташувавши спочатку менший елемент, а потім більший;

    • з двох 2-елементних частин утворюють одну 4-елементну частину, порівнюючи елементи двох масивів, починаючи з початку. Менший з них записують у новостворений масив. Потім у масиві, елемент якого виявився меншим, переходять до наступного елемента. Далі продовжують порівнювати перші з незаписаних у новий масив елементів і формувати таким чином новий масив. У випадку, якщо одну з частин буде вичерпано, елементи іншої дописують у новостворений масив у тому самому порядку;
  3. В кінці операції злиття елементи новоутвореного масиву перезаписують у початковий масив.

Розіб'ємо задачу впорядкування масиву A із n елементів на простіші підзадачі, кожну з яких розв'яжемо окремо.

Нехай k — натуральне число. Розіб'ємо масив A на частини довжини k, вказавши діапазони зміни індексу (номера) елемента: 1..k, (k + 1)..2k і т.д. Назвемо масив k-впорядкованим, якщо кожну з цих частин довжини k впорядковано.

Будь-який масив 1-впорядкований. Якщо масив k-впорядкований, і n ≤ k, то він впоряд­кований.

Загальна схема алгоритму має такий вигляд:

k:=1;
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 — номер елемента масиву В, якому останнім було змінено значення.

На кожному кроці злиття виконують одну з двох послідовностей вказівок:

Першу послідовність вказівок (взяти елемент з першої частини) виконують при одночасному справдженні таких двох умов:

Інакше виконують другу послідовність вказівок. Якщо обидві частини не вичерпано, і перші не враховані елементи в них збігаються, тобто можна брати довільний з них, то буде обрано елемент з першої частини (з меншими індексами). Остаточно маємо:

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. Закріплення вивченого матеріалу


Завдання. Використовуючи фрагменти коду, подані у викладі нового матеріалу, написати програму, яка:

Програму записати з назвою Ваше прізвище у теку, вказану вчителем.

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання

  1. Порівняти створену у класі програму з демонстраційними розв'язанням.

  2. Переглянути хореографічну ілюстрацію методу.

  3. Ознайомитися з використанням методу злиття у розв'язуванні задач учнівських олімпіад з інформатики — див. опис розв'язання задачі 3 «Істотні інверсії» ІІІ етапу за матеріалами журнальної публікації.


Текст упорядкувала Анікіна Лариса Павлівна, вчитель гімназії № 143 Оболонського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 24.11.2014 по 12.12.2014.