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

Мета:

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

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

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

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

Хід уроку

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

2. Актуалізація опорних знань.

Дати пояснення до вказівок і порівняти з очікуваним:

import java.util.Arrays; — імпорт бібліотеки для роботи з масивами;

import java.util.Random — імпорт бібліотеки для породження випадкового числа;

int[] a = new int[10] — ініціалізація масиву a цілих чисел довжини 10;

for (int j=0; <=n; j++) {вказівка} — виконати вказівку n разів;

while (висловлювання) {вказівка} — поки справджується висловлювання, виконувати вказівку;

System.out.print(Arrays.toString(а)); — виведення масиву а на екран (консоль);

Random g = new Random() — створення змінної g, яка вказуватиме на екземпляр класу Random для звернення до методів цього класу;

a[j] = g.nextInt(10) — надання елементу масиву a з індексом j випадкового цілого значення з діапазону 0..9.

3. Вивчення нового матеріалу

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

• простота у реалізації;

• ефективний (зазвичай) на коротких масивах;

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

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

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

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

Примітка. Метод вибору чергового елементу з початкового списку може бути довільним при формуванні нового масиву.

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

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

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

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

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

Текст упорядкувала Хачатрян Сюзанна Акопіківна, вчитель НВК № 141 «ОРТ» м. Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 12.11.2018 по 16.11.2018.