СОРТУВАННЯ МЕТОДОМ ОБМІНУ. ПОШУК У СПИСКАХ ДАНИХ, ЯКІ ВІДПОВІДАЮТЬ ПЕВНИМ УМОВАМ
Урок 12
Матеріали для виконання
завдань, вправ та
файли-заготовки
Поміркуйте
Проблема x = y, y = x
Якщо виконати ці команди послідовно, значення x буде втрачено на першому кроці. В обох змінних залишиться значення y.
Наприклад: х=5, у=10.
Після х=у: х=10, у=10.
Після у=х: х=10, у=10.
Правильні способи
temp = x; x = y; y = temp;
x, y = y, x
Ідея методу обміну ("Бульбашка")
Алгоритм порівнює сусідні елементи списку. Якщо лівий елемент більший за правий — вони міняються місцями.
Метод отримав назву за аналогією з бульбашками у воді: найбільші елементи поступово "спливають" у кінець списку.
Алгоритм у дії
(Покрокова демонстрація)
Рядок із чисел: [13, 6, 5, 18, 11, 10].
Результат: число 18 зайняло своє фінальне місце!
Скільки потрібно проходів?
проходів для списку з 6 елементів
Логіка циклів
Для повного сортування списку довжиною n потрібно виконати n-1 прохід. На кожному наступному кроці кількість порівнянь зменшується, оскільки останні елементи вже відсортовані.
Метод обміну простий у реалізації, але повільний для дуже великих масивів даних.
Реалізація на Python
У внутрішньому циклі діапазон n-1-i дозволяє не перевіряти вже "спливлі" великі числа.
Обговоріть і зробіть висновки
1. Як змінити наведений проєкт, щоб він сортував списки за спаданням?
2. Чи правильно сортуватимуть дані у списку вищенаведені проєкти, якщо список міститиме рівні між собою числа? Відповідь поясніть.
3. На яку одну команду можна замінити три останні команди циклу в наведеному проєкті?
Візуалізація методу вибору
Сторінки історії. Світовий контекст
Джон фон Нейман
Створив алгоритм сортування злиттям (Merge Sort) (1945 рік). Один із батьків архітектури сучасних комп'ютерів.
Чарльз Хоар
Розробив швидке сортування (QuickSort) (1959 рік) — один із найпопулярніших та найефективніших алгоритмів у світі.
Дональд Кнут
Автор фундаментальної праці «Мистецтво програмування» Людина, яка першою детально математично проаналізувала всі методи сортування.
Дональд Шелл
Винайшов сортування Шелла (Shellsort) (1959 рік) — покращений метод сортування включенням, який працює значно швидше за прості алгоритми.
Едсгер Дейкстра
Творець алгоритмів на графах та співавтор алгоритму плавного сортування (Smoothsort).
Українська школа.
Інститут кібернетики
ім. В. М. Глушкова
Українські науковці також багато років займаються вдосконаленням та застосуванням алгоритмів сортування для оптимізації обчислень.
Проблемами сортування даних займалися дослідники Інституту кібернетики імені В. М. Глушкова НАН України для організації обчислень на комп’ютерах із розподіленою пам’яттю.
Сучасне застосування та українські вчені
Суттєвий внесок у ці дослідження зробили українські вчені М.І. Жалдак та Ю.В. Триус. Завдяки їхнім фундаментальним працям із символьної обробки даних сьогодні ми маємо технології, без яких не уявляємо свого життя.
Жалдак Мирослав Іванович
Триус Юрій Васильович
Сортування лежить в основі розпізнавання образів (наприклад, FaceID), у роботі штучного інтелекту, нейромереж та у швидких хмарних сховищах.
Пошук даних у списках
Операція in
Перевіряє наявність значення у списку.
Повертає True або False.
Метод count()
Визначає, скільки разів певне значення трапляється у списку.
Метод index()
Повертає індекс першого входження вказаного значення.
Задачи на пошук та вставку
Задача 1. Визначити, чи є введене число у списку. Якщо так, то скільки разів воно трапляється у списку і з якими індексами.
Використавуваємо операцію in.
Задачи на пошук та вставку
Задача 2. Є список із чисел, упорядкований за неспаданням, і є окреме число. Уставити це окреме число у список, не порушуючи його впорядкованість.
Оскільки список упорядковано за неспаданням, то кожне наступне число в ньому, починаючи з другого, не менше (більше або дорівнює) від попереднього.
Задача. Скласти проєкт для введення значень елементів одно вимірного масиву з 10 дійсних чисел, упорядкування цього масиву за незростанням методом обміну і виведення впорядкованого.
Працюємо з комп’ютером
Увага! Під час роботи з комп’ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.
Урок 13. РЯДКОВІ ВЕЛИЧИНИ
Готуємось до вивчення нового матеріалу
Матеріали для виконання
завдань, вправ та
файли-заготовки