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

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

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

Обладнання: ПК з встановленими ОС і інтерпретатором Ruby або стійким сполученням з Інтернетом для роботи з online-сервісами, (дана) інструкція.

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

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

Хід уроку

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

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

Масив — згруповані за місцем розташування у пам'яті величини (як правило) одного типу, що мають одну назву (ідентифікатор) і різні порядкові номери (індекси). Це поняття програмування відповідає математичним поняттям послідовності й таблиці (матриці).

Елемент масиву — одна з величин, що утворюють масив. Це поняття програмування відповідає математичному поняттю елемента послідовності чи матриці.

Індекс масиву — величина перелічуваного (зазвичай цілого) типу, яка (сукупність яких) вказує на конкретний елемент масиву. Це поняття програмування відповідає математичному поняттю номера елемента послідовності чи номеру рядка/стовпчика таблиці (матриці).

Масив має такі властивості:

• тип елементів (масиву) для типізованих мов;
• назва (ідентифікатор) — одна й та сама для всіх елементів масиву;
• розмірність — кількість номерів (індексів), необхідних для визначення розташу­вання елемента у масиві;
• діапазони зміни номерів (індексів).

Мова Ruby є динамічно типізованою. Для масивів це означає: типи елементів масиву можна змінювати протягом виконання коду і для різних елементів по різному.

• зчитування з файлу:

  a = []
  File.open("input.txt", "r") do |f| # відкрити файл input.txt для читання і
                                     # передати посилання на нього через змінну f
    f.each do |line|                 # для кожного рядка (line) з файла
      a.push(line)                   # додати рядок до масиву
    end
  end                                # при виході з блоку файл буде закрито автоматично

  або те саме одним рядком:
  
  a = File.readlines('input.txt')

• cтворення масива, значення елементів якого визначають згідно з формулою (далі подано приклади створення масиву з n елементів, значення j-го елемента якого дорівнює j ∙ (j + 1) − 1:

  a = []
  for j in (0..n-1) do
    a[j] = j*(j+1)-1
  end

  або так:

  a = []
  (0..n-1).each do |j|
    a[j] = j*(j+1)-1
  end

  або з використанням метода new класу Array:

  a = Array.new(n) { |j| j*(j+1)-1 }

• з використанням генератора випадкових чисел (далі подано приклад створення масиву з n випадкових чисел, що набувають значень з проміжку [x, y]:
  
  a = Array.new(n) { |j| rand(x..y) } або
  
  a = Array.new(n) { rand(x..y) }

Способи виведення елементів масиву

• Вказівка print(a) виводить елементи масиву a у квадратних дужках через кому. Наприклад, код
  
  a = [1, 2, 3]
  print(a)
  
  виведе:
  
  [1, 2, 3]

• Вказівка puts(a) виводить елементи масиву з ознакою кінця рядка після кожного. Наприклад, код
  
  a = [1, 2, 3]
  puts(a)
  
  виведе:
  
  1
  2
  3

• Виведення масиву в файл подамо прикладом запису значень елементів масиву a в окремі рядки файлу filename.txt:

  File.open("filename.txt", "w+") do |f|
    a.each { |element| f.puts(element) }
  end

  або:

  File.open("filename.txt", "w+") do |f|
    f.puts(a)
  end

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
  end
  … # злити підмасиви з індексами t+1..q і q+1..r
  t=r;
end

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

Запровадимо такі позначення:
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)||((q0<r) && (A[p0]<=A[q0])))) — другу частину вичерпано (q0==r) або її не вичерпано (q0<r), але черговий елемент у ній не менший від чергового елемента першої частини.

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

p0=t
q0=q
s0=t
while ((p0!=q) || (q0!=r))
  if ((p0<q) && (((q0==r)||((q0<r) && (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
  end
end 

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

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

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

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

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

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

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

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

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

Текст упорядкував Шевчук Станіслав Олегович, вчитель гімназії № 283 Деснянського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 29.10.2018 по 02.11.2018. У роботі використано матеріали роботи Анікіної Лариси Павлівни.