• назва (ідентифікатор) — послідовність літер латиниці, цифр і нижнього підкреслювання «_», на початку — обов'язково літера;

• тип — визначає обсяг відведеної пам'яті, можливі дії, правила тлумачення бітів пам'яті та множину допустимих значень;

• розмірність — проста або складена (структурована);

• значення — елемент множини допустимих значень величини.

З кожною величиною (або її складовою для структурованої величини) пов'язана ділянка оперативної пам’яті, куди її під час роботи програми заносять та у якій зберегають. Цю ділянку визначено її адресою. Тут під адресою розуміють адресу першого байту з послідовновних щодо адресації байтів, відведених для збереження величини. Назва змінної слугує назвою цієї послідовності байтів під час виконання програми.

Змінні — вид даних, значення яких дозволено змінювати протягом виконання програми.

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

Оголошення змінної у JavaScript здійснюють таким чином:

var назва змінної1; // давніший варіант
let назва змінної2;

Відмінності між цими варіантами настільки тонкі, що початківці їх не відчувають. І досі збережено можливість створити змінну наданням значення без використання службових слів var чи let. Але лише за умови відсутності use strict у файлах кодів.

Оголошення сталої у JavaScript здійснюють таким чином:

const назва сталої;

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

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

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

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

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

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

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

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

Примітка. У мові Javascript з динамічною типізацією змінних тип змінної можна змінюти разом зі значенням. Тому й елементами масиву можуть бути різні за типом змінні.

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

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

Елемент масиву може мати і тип простої (неструктурованої) величини і складений тип (масиву, рядка тощо), тобто може існувати масив масивів, масив рядків тощо. Глибину вкладеності (а значить, і кількість індексів) необмежено, але загальну довжину структури обмежено.

Порядок роботи з масивом

1. Створити масив.
2. Заповнити масив значеннями.
3. При потребі еревірити правильність заповнення.
4. Опрацювати масив.
5. Вивести отримані результати.

Під час розв'язування задач переважно використовують одновимірні та двовимірні масиви.

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

Двовимірний масив інакше називають таблицею або матрицею. Кожному його елементу ставлять у відповідність два індекси: номер рядка та номер стовпчика. Прикладом двовимірного масиву є шахівниця.

Примітка. Використання масивів розмірності 2 і більше зумовлено лише міркуваннями зручності для програмістів. Наприклад, існує взаємно однозначна відповідність j = kn + l між індексом j — у межах від 0 до (mn – 1) і парою індексів (k, l) при k — у межах від 0 до (m – 1), l — у межах від 0 до (n – 1). А саме: при діленні j на n маємо: k — частка, l — лишок.

Створення масиву

назва_масиву = new Array();

Розмір масиву буде визначено за результатами заповнення.

Примітка. Подані далі (за гіперпосиланнями) програми бажано не лише споглядати, але й протестувати, використавши браузер та його середовище розробника (для Mozilla Firefox натиснути клавіші Ctrl + Shift + K).

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

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

Примітка. У перших трьох прикладах елементам масиву надано числових значень, в останніх двох — рядків (програма мовою Javascript зчитуює і записує лише рядки). Для перетворення рядка у число використовують функцію Number, для перетворення числа у рядок — String.

Обчислення суми елементів масиву здійснюють, надавши деякій змінній початкового нульового значення, яке змінюють послідовним додаванням всіх елементів масиву у циклі — див. приклади для 1- і 2-вимірного масивів.

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

• залежністю часу роботи від кількості елементів масиву;
• залежністю додаткової пам'яті від кількості елементів масиву;
• cтійкістю роботи.

Впорядкування елементів масиву вибором найменшого (найбільшого) елемента (опис подано для лінійного масиву з діапазоном індексу 0..n)

Змінюючи j від 0 — найменшого значення індексу — до (n – 1) — найбільшого значення індексу, зменшеного на 1, — робимо таке:

• визначаємо номер l найменшого (найбільшого) елемента для індексів у межах від j до n включно;

• міняємо місцями значення елементів з індексами j та l. У результаті такої заміни на місце з номером (індексом) j стане те значення, що потрібно.

Подамо для наочності ілюстрацію такого впорядкування 10-елементного масиву, запозичену зі сторінки Вікіпедії.

Тут червоним тлом виділено те значення, яке серед елементів з номером від j до n вважають найменшим у поточний момент виконання алгоритму, блакитним — значення поточного елемента масиву, яке порівнюють з тим, що наразі вважають найменшим, жовтим — ті значення, які вже стоять на потрібному місці. Див. приклад програми мовою Javascript.

Метод швидкого сортування
Основу цього алгоритму розробив у 1962 році британський учений Чарлз Ентоні Річард Гоар (Charles Antony Richard Hoare). Рекурсивний алгоритм для впоряд­кування за неспаданням масиву зі значеннями індексів від l до r включно має такий вигляд:

1. Вибирати значення елемента масиву.

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

3. Якщо l < (j – 1), виконати алгоритм для індексів від l до (j – 1) включно.

4. Якщо (j + 1) < r, виконати алгоритм для індексів від (j + 1) до r включно.

Пункт 2 цього алгоритму можна деталізувати:

• надати змінним i, j значення l, r відповідно;
• збільшувати значення l, поки l-й елемент менший від обраного;
• збільшувати значення r, поки r-й елемент більший від обраного;
• при l < r:
  • поміняти місцями елементи з індексами l і r;
  • збільшити значення l на 1;
  • зменшити значення r на 1.

Рекурсивність алгоритму означає виклик цього алгоритму в ньому самому — див. кроки 3–4. На малюнку нижче подано частину схеми впорядкування.

Тут кольоровими кругами позначено вибрані значення елементів масиву. Після переставлянь навколо них ці значення надалі залишаються нерухомими у масиві. Спочатку буде впорядковано елементи, менші від значення, позначеного зеленим кольором, потім — менші від значення, позначеного червоним кольором, ще пізніше — менші від значення, позначеного синім кольором.

Примітка. Поданий вище запис стане алгоритмом лише після того, як буде деталізовано вибір значення. У багатьох описах алгоритму можна зустріти вибір елемента з найменшим чи з найбільшим номером. Розглянемо спробу впорядкувати вже впорядкований масив при такому виборі. Глибина занурення — кількість послідовних викликів рекурсивного алгоритму без виходу з нього — буде майже збігатися з довжиною масиву. Останнє може призвести до переповнення стеку частини оперативної пам'яті, куди програма заносить дані про виклик програмі та функцій, їхні аргументи, точку повернення тощо. А переповнення стеку означає аварійне завершення роботи. Який би не був детерміністичний (без випадковостей) вибір значення (наприклад, із середини масиву), завжди можна вказати вхідні дані, для яких глибина занурення для цих вхідних даних лише на 1 відрізнятиметься від довжини масиву. Тому вибір потрібно робити з використанням генератора випадкових чисел. І в цьому випадку можливе переповнення стеку, але ймовірність цієї події настільки мала, що аварійне припинення роботи зазвичай не відбувається.

Проаналізуйте на відповідність опису ілюстрацію для вибору правого краю (елемента з найбільшим номером), запозичену із сайту http://uk.wikipedia.org/wiki

Див. приклад програми мовою Javascript.

Іншими словами про це кажуть так: часові складності алгоритмів дорівнюють відповідно O(n²), O(n log₂n) і O(n + m). У більшості випадків доречно використати саме швидкий метод Хоара, хоча бувають випадки, коли для розв'язування поставленої задачі (не лише впорядкування) потрібно використати, наприклад, метод злиття, або використати метод обліку, щоб задовольнити обмеження на час виконання програми. Обидва випадки зустрічалися на ІІІ (міському) етапі Всеукраїнської учнівської олімпіади з інформатики у місті Києві.

Насправді досвідчені програмісти не програмують методи упорядкування окрім тих випадків, у яких упорядкування є основою розв'язання істотно складнішого алгоритму. Зазвичай використовують такі вбудовані методи мови Javascript:

• sort — для упорядкування за зростанням;
• reverse — для упорядкування за спаданням.

Але як усталено ці методи працюють з елементами масиву як з рядками — див. приклад.

Для роботи з числовими значеннями потрібно використати аргумент методу sort — функцію двох аргументів, яка повертає:

• 0, якщо порядок значень неістотний;
• −1, якщо значенню першого аргумента надають менший номер;
• +1, якщо значенню першого аргумента надають більший номер.

— див. приклад.

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

Алгоритм двійкового (бінарного) пошуку використовують для пошуку (індекса) елемента масиву з певним значенням. Цей алгоритм застосовують до попередньо упорядкованого лінійного масиву при розташуванні заданого значення елемента між найбільшим та найменшим значеннями елементів масиву. За рахунок упорядкованості масиву досягають великої швидкості пошуку — кількість операцій пропорційна log₂ N, що позначають таким чином: O(log₂ N).

Головна ідея двійкового пошуку — з кожним наближенням поділяти множину значень (приблизно) навпіл.

Для стислого опису алгоритму запровадимо такі позначення для змінних, початкові значення яких задають на початку виконання алгоритму:

j — менша межа діапазону номерів, на якому шукають потрібний номер, дорівнює меншій межі діапазону номерів масиву;

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

Алгоритм бінарного пошуку має такий вигляд:

1. Поки справджується нерівність j ≤ k, робити таке:

   • надати значення змінній l = [(j + k)/2] — знайти індекс l, що поділяє досліджуваний діапазон навпіл;

   • якщо a_l = b, завершити пошук зі знайденим номером l;

   • якщо a_l < b, надати значення змінній j = (l + 1), тобто вибрати для подальшого пошуку діапазон, розташований правіше від l;

   • якщо a_l > b, надати значення змінній k = (l – 1), тобто вибрати для подальшого пошуку діапазон, розташований лівіше від l.

2. Завершити пошук, вважаючи його неуспішним.

Тут квадратні дужки (у першій дії всередині циклу) позначають операцію визначення цілої частини або округлення до найближчого цілого числа. Див. приклад.

5. Закріплення вивченого матеріалу

1. Що таке масив?
2. Які властивості має масив?
3. Що таке форма масиву?
4. Як описують масив?
5. Які методи упорядкування лінійних масивів Ви знаєте?
6. У чому полягає упорядкування масиву швидким методом Хоара?
7. У чому полягає бінарний пошук?

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

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

1. Вивчити матеріал уроку.
2. Написати програму розв'язання такої задачі: заповнити лінійний масив випадковим чином і визначити, скільки разів досягається найбільше значення у даному масиві та найменший порядковий номер (індекс) для такого найбільшого значення.

Текст упорядкував Олександр Рудик.