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

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

• описує: алгоритм упорядкування злиттям;
• уміє:
  • складати програму упорядкування лінійного масиву злиттям;
  • налагоджувати програму та виконувати її у покроковому режимі
  • використовувати складену програму при розвязанні задач.

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

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

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

Хід уроку

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

2. Актуалізація опорних знань
Відповісти на поставлені питання і порівняти з очікуваним.

1. Що називають упорядкуванням (сортуванням) лінійного масиву? Cортування масиву — один з найрозповсюдженіших видів опрацювання даних. Він полягає у розташуванні об’єктів у певному порядку. Наприклад, чисел за зростанням або за спаданням їх значень, прізвищ у алфавітному порядку тощо.

2. Назвіть методи упорядкування (сортування) масивів? Обмінне сортування (метод «пухирця», «шейкер-сортування), сортування вибором, сортування вставками, швидке сортування, сортування Шелла, пірамідальне сортування, сортування обчисленням адреси, сортування порозрядним групуванням тощо.

3. По яким параметрам проводиться оцінка алгоритмів? За кількістю операцій (часова ефективність) або за об'ємом використаної пам'яті (просторова ефективність). Важлива лише асимптотична складність, тобто порядок зростання цих кількостей при зростанні кількості елементів.

3. Вивчення нового матеріалу

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

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

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

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

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

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

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

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

3. В кінці операції злиття елементи новоутвореного масиву перезаписують у початковий масив.

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

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

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

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

k=1;
while(k<n):
  # перетворити k-упорядкований масив у 2k-упорядкований
  k=k*2

Розглянемо процедуру перетворення k-упорядкованого масиву у 2k-упорядкований. Згрупуємо всі підмасиви довжиною k у пари підмасивів. Тепер пару упорядкованих підмасивів зіллємо в один упорядкований підмасив. Виконавши це зі всіма парами, отримаємо 2k-упорядкований масив.

t=0;
while ((t+k)<=n):
  q=t+k
  if(t+2*k>=n):
    r=n
  else:
    r=t+2*k
  # злити підмасиви з індексами t+1..q і q+1..r
  t=r

Злиття вимагає використання допоміжного масиву В для запису результатів злиття.

Запровадимо такі позначення:
p₀ і q₀ — номери перших елементів частин масиву, які потрібно злити;
s₀ — номер елемента масиву В, якому потрібно змінити значення.

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

• або
  B[s0]=A[p0]
  p0=p0+1
  s0=s0+1


• або
  B[s0]=A[q0]
  q0=q0+1
  s0=s0+1

• p0 < q — першу частину ще не вичерпано;

• (((q0==r) or ((q0<r) and (A[p0]<=A[q0])))) — другу частину вичерпано (q0==r) або її не вичерпано (q0<r), але черговий елемент у ній не менший від чергового елемента першої частини.

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

      p0=t
      q0=q
      s0=t
      while ((p0!=q) or (q0!=r)):
        if ((p0<q) and (((q0==r) or ((q0<r) and (A[p0]<=A[q0]))))):
             B[s0]=A[p0]
             p0=p0+1
             s0=s0+1
        else:
             B[s0]=A[q0]
             q0=q0+1
             s0=s0+1

Недоліком упорядкування злиттям є використання додаткової пам'яті для збереження масиву такого самого розміру, як і той, що упорядковують. Перевагами алгоритму є його стійкість (він не міняє місцями однакові за значенням елементи) та прийнятна ефективність O(n log n).

4. Інструктаж з ТБ
5. Закріплення вивченого матеріалу

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

• зчитає з єдиного рядка файлу input.txt цілі значення елементів масиву;
• упорядкує лінійний масив методом злиття;
• запише у файл output.txt елементи масиву у порядку неспадання.

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

Вказівка до виконання завдання. Використати такий код програми, що зчитує з файлу input.txt цілі значення елементів масиву і записує у файл output.txt ці елементи у тому самому порядку.

f=open("input.txt","r")
A=f.readline().split()
f.close
n=len(A);
for i in range(n):
      A[i]= int(A[i])

f = open("output.txt","w")
f.write(str(A[0]))
for j in range(1,n):
  f.write(" "+str(A[j]))
f.write("\n")
f.close()

Всі обчислення, опрацювання вхідних даних виконувати на місці порожнього рядка.

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

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

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

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

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

Текст упорядкував Олександр Рудик. У роботі використано матеріали роботи Анікіної Лариси Павлівни.