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

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

Cукупність розмірності й діапазонів називають формою масиву.

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

Наприклад, $а[3] — 3-тій елемент масиву $а, $с[j] — j-ий елемент масиву $с.

Одновимірний масив інакше ще називають лінійним масивом або вектором. Кожному його елементу ставлять у відповідність один індекс. У математиці лінійному масиву відповідає поняття послідовності, а номеру члена послідовності — індекс масиву.

Способи створення масивів:

• Оператор надання значення. Наприклад, код:

  <?php
  $m[0] = "значення";
  $m[1] = 1;
  echo $m[0];
  echo $m[1];
  ?>

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

  <?php
  $m[] = "значення";
  $m[] = 1;
  echo $m[0];
  echo $m[1];
  ?>

• Використання службового слова array() для створення:
  • порожнього масиву:

    <?php
    $m = array();
    ?>

  • масиву з вказаними елементами:

    <?php
    $m = array ("a", 2);
    ?>

Способи заповнення масиву
(подано на прикладі одновимірного масиву):

• зчитування значень елементів з файлу:

  <?php
  $fp = fopen('1.txt','r');
  $i = 0;
  while(!feof($fp)) {$m[$i] = fgets($fp); $i++;}
  $q = $i-1;
  fclose($fp);
  for ($i = 0; $i<$q; $i++) echo $m[$i].' ';
  ?>

• використання генератора випадкових чисел:

  <?php
  for ($i = 0; $i < 9; $i++) {$m[] = rand(0, 99);}
  for ($i = 0; $i < 9; $i++) {echo $m[$i].' ';}
  ?>

• згідно з формулою:

  <?php
  for ($i = 0; $i < 9; $i++) {$m[] = $i*($i+1)/2;}
  for ($i = 0; $i < 9; $i++) {echo $m[$i].' ';}
  ?>

Виведення масиву можна здійснювати на екран:

• на екран — за допомогою оператора echo (див. приклади вище);
• у файл — див. приклад нижче;

  <?php
  for ($i = 0; $i < 9; $i++) {$m[] = $i*($i+1)/2;}
  $f = fopen("new.txt","w+");
  for ($i = 0; $i < count($m); $i++)
    {$record = fwrite($f,$m[$i],' ');}
  fclose($f);
  ?>

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++;  $s0++;;
• або  $B[$s0]=$A[$q0];  $q0++;  $s0++;

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

• (q₀ = r) ∨ ((q₀ < r) ∧ (A[p₀ + 1] ≤ A[q₀ + 1])) — другу частину вичерпано (q₀ = r) або її не вичерпано (q₀ < 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++;  $s0++;}
  else { $B[$s0]=$A[$q0];  $q0++;  $s0++;}
}

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

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

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

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

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

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

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

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

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

Текст упорядкувала Шевченко Ірина Анатоліївна, вчитель гімназії "Грейс" Деснянського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 10.12.2018 по 14.12.2018.