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

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

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

Найпростішими за формою є масиви розмірності 1 (лише один індекс). Такі масиви називають лінійними або одновимірними чи векторами.

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

Форми оголошення (опису) масиву

• або тип[] назва_змінної;
• або тип назва_змінної[];

Дужки [] вказують лише на те, що змінні розташовано у масиві, але власне масиви ще не існують. Для існування масиву потрібно зарезервувати (виділити) пам'ять за допомогою оператора new.

Загальна форма оператора new щодо одновимірних масивів має такий вигляд:

змінна_масиву = new тип[розмір];

Наприклад,

anArrayOfStrings = new String[9];

Лише після того, як описано масив і для нього зарезервовано пам'ять, можна звертатись до довільного елемента масиву.

Суміщення оголошення і виділення пам'яті для масиву можна здійснити таким чином:

тип назва_змінної[] = new тип[розмір];

У Java нумерацію елементів масиву починають з 0, тому квітню — четвертому місяцю року — відповідає елемент масиву month_days[3] з індексом 3.

Система Java виконує ретельну перевірку того, чи не була випадково здійснено спробу виходу за межі допустимого діапазону значень індексів масиву. Наприклад, у поданій програмі система часу виконання буде перевіряти відповідність значення кожного індексу допустимому діапазону від 0 до 11 включно. Якщо буде спроба звертання до елементів за межами цього діапазону, то це призведе до помилки виконання.

Способи заповнення масиву

1. З клавіатури за допомогою класу Scanner з пакету java.util. Для отримання консольного введення в класі System визначено об’єкт in. З об’єктом System.in не дуже зручно працювати, тому, як правило, використовують клас Scanner, який у свою чергу використовує System.in — див. наступний приклад.

   package work;
   import java.util.Scanner;
   public class work {
     public static void main(String[] args) {
       Scanner input = new Scanner(System.in);
       System.out.println("Input array length: ");
       int size = input.nextInt();  // Зчитування розміру масиву у змінну size
       int array[] = new int[size]; // Створення масиву array розміру size
       System.out.println("Input array elements:");
       for (int i = 0; i < size; i++) {
         array[i] = input.nextInt(); // Заповнення масиву
         }
       System.out.print ("Inserted array elements:");
       for (int i = 0; i < size; i++) {
         System.out.print (" " + array[i]); // Виведення введених раніше значень 
         }
       System.out.println();
       }
   }

   Спочатку імпортують клас Scanner з пакету java.util. Для створення самого об'єкта Scanner у його конструктор передають об'єкт System.in. Після цього можна отримувати значення, які вводять з клавіатури. Наприклад, щоб отримати введене число, використовують метод in.nextInt(), який повертає введене з клавіатури цілочисельне значення. В даному випадку в циклі вводяться всі елементи масиву, а за допомогою іншого циклу всі раніше введені елементи масиву виводяться в рядок.
   
   Клас Scanner має ще кілька методів, які дозволяють отримати введені користу­вачем значення:

   • next() — зчитує введений рядок до першого пробілу;
   • nextLine() — зчитує весь введений рядок;
   • nextInt() — зчитує введене число int;
   • nextDouble() — зчитує введене число double;
   • hasNext() — перевіряє, чи було введене слово;
   • hasNextInt() — перевіряє, чи було введено число int;
   • hasNextDouble() — перевіряє, чи було введено double.

   Методи nextByte / nextShort / nextFloat / nextBoolean класу Scanner за аналогією з nextInt зчитують дані відповідного типу даних.

2. З файлу. Для того, щоб ввести масив з файлу, потрібно запозичити необхідні складові з бібліотеки Java — див. перші рядки поданого далі коду, у якому є звертання до попередньо створеного текстового файлу input_array.txt. Цей файл має містити (у вказаному порядку) кількість елементів масиву та значення елементів цього масиву у порядку зростання номеру елемента.

   package work;
   import java.io.File;
   import java.io.FileNotFoundException;
   import java.util.Arrays;
   import java.util.Scanner;
   public class work {
     public static void main(String[] args) throws FileNotFoundException {
       Scanner scanner = new Scanner(new File("input_array.txt"));
       int size = scanner.nextInt();
       int[] array = new int[size];
       for (int i = 0; i < size; i++) {
         array[i] = scanner.nextInt();
       }
       scanner.close();
       System.out.println("Array: " + Arrays.toString(array));
     }
   }

3. За допомогою методу fill для заповнення всього масиву однаковими значеннями.

   package work;
   import java.util.Arrays;
   public class work {
     public static void main(String args[]) {
       int a[] = new int[5];
       Arrays.fill(a, 5);
       for (int i = 0; i < 5; i++) {
         System.out.print("a[" + i + "]=" + a[i] + "; ");
       }
     }
   }

4. З використанням генератора випадкових чисел Random з двома різними способами ініціалізації:

   • з використанням системих дати й часу (як усталено);
   • з використанням заданого числа типу long.

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

   • nextBoolean();
   • nextInt();
   • nextLong();
   • nextFloat();
   • nextDouble();

   Останні два методи породжують числа з рухомою крапкою лише з проміжку [0; 1], а цілочисельні — з усього діапазону значень. Але цілі числа можна породжувати і з діапазону від 0 до max – 1 включно (при певному натуральному max), якщо писати так: nextInt(max).

   package work;
   import java.util.Random;
   public class work {
     public static void main(String args[]) {
       Random r = new Random();
       int[] a = new int[10];
       for (int i = 0; i < a.length; i++) {
         a[i] = r.nextInt(9);
         System.out.println("a["+i+"]="+a[i]);
       }
     }
   }

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, то він впорядкований.

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

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₀] ≤ A[q₀])) — другу частину вичерпано (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. Закріплення вивченого матеріалу

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

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

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

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

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

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

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

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

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