Тема: упорядкування включенням мовою PHP.

Мета:

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

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

Хід уроку

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

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

1. Що таке алгоритм?
   Алгори́тм — це запис вказівок, що описують порядок дій виконавця з метою досягнути результат розв'язання задачі за скінченну кількість дій.

2. Назвіть основні алгоритмічні структури.
   Лінійна, повторення (цикл), розгалуженням.

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

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

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

6. Назвіть конструкції мови програмування PHP для опису повторень.
   while, for, foreach, do … while.

7. Дати пояснення до вказівок та порівняти з очікуваними:
   • rand(a,b); — породження випадкового цілого числа у межах [a, b);
   • for ($i=0; $i<n; $i++) {вказівка} — виконати вказівку n разів;
   • print_r($a); — вивести масив $a на екран;
   • count($a); — кількість індексів у масиві $a;
   • while (висловлювання) {вказівка} — поки справджується висловлювання, виконувати вказівку.

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

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

Ідея апгоритму. Розглядаючи всі індекси елементів списку у порядку зростання, порівнюємо значення елемента списку з елементами списку, що мають менші індекси і вже упорядковані за зростанням. При виявленні більших значень елементи зсуваються у списку (у сторону збільшення індексу на 1), а на останнє звільнене місце вставляємо значення вибраного елемента — див. ілюстрацію, запозичену зі сторінки Вікіпедії:

Упорядкування (cортування) включенням — простий алгоритм на основі порівнянь з такими перевагами:

• простота у реалізації;
• ефективний (зазвичай) на коротких масивах;
• ефективний при частково упорядкованих даних з продуктивністю O(n + d). Тут n — кількість елементів, d — кількість пар порушень порядку (інверсій);
• на практиці ефективніший за більшість інших квадратичних алгоритмів O(n²), як вибором або бульбашкою.

Реалізація цього алгоритму мовою PHP має такий вигляд. Перевірити коректність роботи програми можна використавши online середовище, наприклад, rextester.

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

1. Назвати переваги упорядкування включенням над іншими квадратичними алгоритмами.
2. Описати метод упорядкування включенням.
3. Програмно реалізувати алгоритм включення для цілих чисел.

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

7. Домашнє завдання
Вивчити матеріал уроку. Програмно реалізувати алгоритм включення для упорядкування рядків тексту, записаних латиницею у файлі по одному у рядку. Поміркувати, наскільки правильно працюватиме алгоритм при роботі з українськими літерами.

Текст упорядкував Андрєєв Денис Валерійович, вчитель середньої загально­освітньої школи № 35 Святошинського району містам Києва, на курсах підвищення кваліфікації з 10.12.2018 по 14.12.2018.