Урок 53-54. Алгоритми впорядкування одновимірних масивів: сортування методом вибору

Тематичний урок «Мистецтво впорядкування. Від хаосу до системи через інженерний підхід»

Критерії оцінювання навчальних досягнень учнів

Інженерний виклик

⚙️ Вхід у роль: Лабораторія автоматизації

Вітаю! Сьогодні ви виступаєте у ролі інженерів-програмістів у центрі розробки робототехніки. Наше завдання — навчити машину самостійно приймати рішення щодо сортування фізичних об'єктів.

Впорядкування даних (сортування) — це фундамент ефективної роботи будь-якої системи: від алгоритму пошуку в Google до системи стабілізації безпілотника. Сьогодні ми опануємо метод вибору — один із найпрозоріших алгоритмів, який дозволяє зрозуміти логіку "механічного" сортування.

Перегляньте презентацію

🛠️ Технічне завдання (ТЗ)

Перш ніж перейти до написання коду для сортування наших прикладних об'єктів (вантажів або деталей), пам'ятайте про інженерний підхід до алгоритмів:

Розділяй та володарюй. Ми не сортуємо все одразу. Ми шукаємо ОДИН об'єкт (найменший або найбільший) і ставимо його на своє місце.
Оптимізація пам'яті. Метод вибору працює «на місці». Нам не потрібен другий порожній масив — ми просто міняємо елементи місцями. Це критично важливо для вбудованих систем із малою пам'яттю (наприклад, мікроконтролери Arduino).

Ваш план дій

Визначте напрямок сортування (зростання чи спадання).
Оберіть стратегію: шукаємо мінімум чи максимум.
Реалізуйте цикл, який крок за кроком зменшує кількість несортованих елементів.

Готові? Запускаємо компіляцію ідей!

Практичне завдання

Увага! Під час роботи з комп'ютером дотримуйтеся правил безпеки та санітарно-гігієнічних норм.

Повторіть правила безпечної роботи за комп’ютером.

Завантажте і встановіть: Середовище програмування Лазарус (для тих, хто не завантажив)

Завдання 1. Інженерія складських роботів (Метод вибору найбільшого)

Контекст

Ви програмуєте логістичного робота для сортувального центру. На конвеєрі стоять 10 вантажів різної ваги (масив X від 1 до 10). Робот має обмежений простір, тому він повинен вишикувати їх у порядку зростання ваги, щоб найважчий об'єкт опинився в самому кінці ряду.

Технічне завдання

Розробіть алгоритм, за якого робот:

Знаходить найважчий вантаж серед доступних.
Міняє його місцями з останнім вантажем у поточному ряду.
Повторює цей процес для решти вантажів, поки весь ряд не буде впорядкований за зростанням:
X[1] < X[2] < ... < X[10].

Хід роботи

1. Відкрийте вікно середовища Lazarus.
2. Розмістіть на формі:
  - два багаторядкових текстових поля заввишки 400 і з вертикальною смугою прокручування;
  - два написи: над першим багаторядковим текстовим полем з текстом Елементи масиву і над другим – з текстом Елементи за зростанням;
  - кнопку з текстом Сортувати.
3. Створіть обробник події Click для кнопки і введіть у нього такий текст:

var X: array[1 ..10] of real; M, i, k: integer; C, Max: real;
begin
For i := 1 to 10 do
X[i] := StrToFloat(Memo1.Lines[i-1]); // формування одновимірного масиву X з 10 чисел
For k := 10 downto 2 do
begin
М := 1; Max := Х[1]; // М — номер Мах(Х[1..К])
For і := 2 to k do
If X[i] > Max
Then begin
Max := X[i]; M := i;
end;
C := X[M]; X[M] := X[k]; X[k] := C; {перестановка X[K] і Х[М]}
end;
For i := 1 to 10 do
Memo2.Lines.Append(FloatToStr(X[i])); // виведення у друге багаторядкове поле елементи масиву Х
end;

1. Запустіть проєкт на виконання.
2. Уведіть у перше багаторядкове поле числа: 21; 27; 15; 20; 1; 29; 12; 18; 26; 2. Виберіть кнопку Сортувати. Проаналізуйте отриманий результат.
3. Видаліть числа з першого багаторядкового поля і введіть інші: –16; 98; –43; 46; 0; 45; –1; 29; –2,67; 55. Виберіть кнопку Сортувати. Проаналізуйте отриманий результат.
4. Видаліть числа з першого багаторядкового поля і введіть інші: 16; 98,28; 14; 0; 45; 1; 29; 2,67; 55; 10. Виберіть кнопку Сортувати. Проаналізуйте отриманий результат.
5. Уведіть свій набір чисел до першого багаторядкового поля. Виберіть кнопку Сортувати. Проаналізуйте отримані результати.
6. Зробіть скриншот виконаного завдання та надішліть його вчителю.
7. Закрийте вікно виконання проєкту.
8. Закрийте вікно середовища Lazarus.

Завдання 2. Оптимізація деталей на 3D-принтері (Метод вибору найменшого)

Контекст

Під час підготовки до серійного друку інженер отримав дані про товщину 6 тестових деталей (масив a від 0 до 5) у міліметрах. Для калібрування екструдера деталі потрібно проаналізувати, починаючи з найтоншої.

Технічне завдання

Напишіть програму, яка впорядкує дані про товщину деталей за зростанням (a[0] < a[1] < ... < a[5]):

Скануйте масив, щоб знайти деталь із найменшою товщиною.
Поставте її на першу позицію (індекс 0), обмінявши з тією деталлю, що там була.
Продовжуйте пошук найменшого елемента серед тих, що залишилися, щоб заповнити наступні позиції.

Хід роботи

Відкрийте вікно середовища Lazarus.
Розмістіть на формі:

два багаторядкових текстових поля заввишки 400 і з вертикальною смугою прокручування;
два написи: над першим багаторядковим текстовим полем з текстом Елементи масиву і над другим – з текстом Елементи за зростанням;
кнопку з текстом Сортувати.

3. Створіть обробник події Click для кнопки і введіть у нього такий текст:
var a: array [0..5] of real; i, j, nmin: integer; min: real;
begin
for i := 0 to 5 do
a[i] := StrToFloat(Memo1.Lines[i]); // уведення значень елементів одновимірного масиву з 6 дійсних чисел
for i := 0 to 4 do // 5 разів повторюємо
begin
min := a[i]; nmin := i; // перший елемент невпорядкованої поки що частини одновимірного масиву
вважаємо найменшим і його номер – номером найменшого
for j := i+1 to 5 do // переглядаємо елементи масиву, починаючи з наступного і до останнього, можливо
серед них є менший, ніж той, який ми на даний момент вважаємо найменшим
у невпорядкованій частині
if a[j]<min then begin min := a[j]; nmin := j; end; // якщо зустрічається елемент, менший ніж той, який
ми вважаємо найменшим у невпорядкованій частині масиву, він стає найменшим і
його номер стає номером найменшого
a[nmin] := a[i]; // на місце знайденого найменшого елемента невпорядкованої поки що частини
одновимірного масиву ставимо перший елемент невпорядкованої частини масиву
a[i] := min // на місце першого елемента невпорядкованої поки що частини одновимірного
масиву ставимо знайдений найменший
end;
Memo2.Clear;
for i := 0 to 5 do Memo2.Lines.Append(FloatToStr(a[i])); // виведення впорядкованого одновимірного масиву

Запустіть проєкт на виконання.
Уведіть у перше багаторядкове поле числа: 21; 27; 15; 20; 1; 29. Виберіть кнопку Сортувати. Проаналізуйте отриманий результат.
Видаліть числа з першого багаторядкового поля і введіть інші: –16; 98; –43; 46; 0; 45. Виберіть кнопку Сортувати. Проаналізуйте отриманий результат.
Видаліть числа з першого багаторядкового поля і введіть інші: 45; 1; 29; 2,67; 55; 10. Виберіть кнопку Сортувати. Проаналізуйте отриманий результат.
Уведіть свій набір чисел до першого багаторядкового поля. Виберіть кнопку Сортувати. Проаналізуйте отримані результати.
Зробіть скриншот виконаного завдання та надішліть його вчителю.
Закрийте вікно виконання проєкту.
Закрийте вікно середовища Lazarus.

📤 Як здати роботу

Збережіть усі файли та скриншоти.
Завантажте їх у розділ Ваші роботи на платформі Google ClassRoom.

Відео в допомогу

Інженерні доповнення

💡 Про енергоефективність

В інженерії кожен "обмін" (swap) елементів у пам'яті споживає мізерну частку енергії. У великих дата-центрах сортування гігантських масивів може коштувати тисячі доларів за електрику. Метод вибору цікавий тим, що він робить мінімальну кількість переміщень елементів (N-1), навіть якщо він не є найшвидшим.

💡 Надійність

Інженери обирають метод вибору там, де важлива передбачуваність. Час виконання цього алгоритму майже не залежить від того, чи був масив уже частково посортований, чи ні. Це дозволяє точно розрахувати час відгуку системи (Hard Real-Time Systems).

Виконайте завдання за підручником

"Інформатика, 9 клас" (Й.Я. Ривкінд та їнші):

Прочитайте та розберіть теоретичний матеріал пункту 5.3 (стор. 258-262).
Виконайте вправи 1, 2 (стор. 268).

Для моніторингу засвоєння знань пройдіть тестування

https://vseosvita.ua/test/start/swu039

Рефлексія та Release Notes

📊 Звіт про тестування (Підсумки)

Вітаємо, інженери! Ви успішно реалізували алгоритм сортування методом вибору. Давайте проаналізуємо наші результати:

Чи працює модель? Якщо ваші вантажі вишикувалися в ряд від найлегшого до найважчого — алгоритм валідний.
Що можна покращити? Подумайте, чи зможе цей алгоритм так само швидко впорядкувати не 10, а 10 000 елементів? (Це запитання для наших наступних досліджень).
Де це знадобиться? Наступного разу, коли ви побачите, як сортуються товари за ціною в інтернет-магазині, пам'ятайте — в основі лежить саме така логіка перебору та порівняння.

Ваш статус сьогодні: Ready for Deployment (Готовий до впровадження).

До зустрічі на наступному етапі розробки!

Page updated

Google Sites

Report abuse