Тема: упорядкування включенням (вставками) мовою Javascript

Мета:

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

Обладнання: комп'ютери зі встановленими ОС та браузером, (дана) інструкція.

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

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

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

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

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

Math.floor(x) — округлення x до цілого з недостачею;
Math.ceil(x) — округлення x до цілого з надвишком;
Math.round(x) — округлення x до найближчого цілого;
Math.random() — випадкове число з [0, 1];
a.length — довжина масиву a;
print(a) — виведення a в середовищі online;
console.log(a) — виведення a в середовищі розробника;
for(i = 0; i < n; i++) — повторити для усіх i = 0, 1, …, n − 1;
while (умова) {вказівка} — поки справджується умова, повторювати виконання вказівки.

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

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

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

Ідея алгоритму. На кожному кроці алгоритму вибирають один з елементів вхідних даних і вставляють його на потрібну позицію в уже упорядкованому масиві доти, доки набір вхідних даних не буде вичерпано. Як в і будь-якому іншому алгоритмі сортування, зі збільшенням розміру масиву збільшується і час упорядкування. Основною перевагою алгоритму сортування вставками є можливість упорядкувати масив по мірі його отримання. Тобто маючи частина масиву, можна починати його упорядкування. При паралельних обчисленнях така особливість відіграє не останню роль.

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

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

Програмна реалізація мовою Javascript має такий вигляд.

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

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

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

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

Текст упорядкувала Єгорова Ірина Володимирівна, вчитель спеціалізованої школи І ступеня № 322 з поглибленим вивченням англійської мови Деснянського району, під час виконання випускної роботи на курсах підвищення кваліфікації з 26 по 30 листопада 2018 року.