СОРТУВАННЯ ДАНИХ У СПИСКАХ. СОРТУВАННЯ МЕТОДОМ ВИБОРУ

Урок 11

Матеріали для виконання

завдань, вправ та

файли-заготовки

Актуалізація знань

Який набір даних вважається відсортованим?

Як сортуються дані в таблицях Excel?

Чим відсортований набір даних кращий за невідсортований?

Пошук потрібних даних у відсортованих наборах відбувається значно швидше.

Приклад: Алфавітний список учнів у класному журналі потрібен саме для зручності та швидкого пошуку.

Що таке відсортований список?

Список вважається відсортованим, якщо між його елементами виконується сталий логічний зв'язок.

За зростанням

a[i+1] > a[i]

Кожне наступне значення більше за попереднє.

За спаданням

a[i+1] < a[i]

Кожне наступне значення менше за попереднє.

За неспаданням

a[i+1] ≥ a[i]

Кожен наступний елемент не менший (більший або дорівнює) за попередній.

За незростанням

a[i+1] ≤ a[i]

Кожен наступний елемент не більший (менший або дорівнює) за попередній.

Вбудовані інструменти Python. Метод sort()

Метод sort() сортує безпосередньо початковий список (початковий стан не зберігається). Працює дуже швидко.

За зростанням

​

За спаданням

​

a.sort()

a.sort(reverse=True)

Сортування методом вибору

Вбудований метод sort швидкий, але складний для розуміння зсередини. Тому розглянемо простіший алгоритм — метод вибору.

Суть алгоритму (для сортування за зростанням):

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

Покроковий приклад методу вибору

Початковий список (6 чисел): [23, 7, 4, 16, -2, 10]

Крок 1:

• Найменший елемент: -2.
• Міняємо місцями з першим (23).
• Результат: [-2, 7, 4, 16, 23, 10] (число -2 на своєму місці).

Крок 2:

• Шукаємо найменший серед [7, 4, 16, 23, 10]. Це 4.
• Міняємо місцями з першим елементом невідсортованої частини (7).
• Результат: [-2, 4, 7, 16, 23, 10].

Покроковий приклад методу вибору

Крок 3:

• Шукаємо найменший серед [7, 16, 23, 10]. Це 7.
• Він уже стоїть на своєму місці, обмін із самим собою.
• Результат: [-2, 4, 7, 16, 23, 10].

Крок 4:

• Шукаємо найменший серед [16, 23, 10]. Це 10.
• Міняємо місцями з 16.
• Результат: [-2, 4, 7, 10, 23, 16].

Крок 5:

• Шукаємо найменший серед [23, 16]. Це 16. Міняємо з 23.
• Фінальний результат: [-2, 4, 7, 10, 16, 23]. (Для списку із 6 елементів ми виконали дії рівно 5 разів).

Проєкт 1. Реалізація через вкладені цикли

Проєкт 2: Реалізація через вбудовані функції min() та index()

Обговоріть і зробіть висновки

• Як змінити ці проєкти, щоб вони сортували списки за спаданням?

2. Чи правильно працюватимуть алгоритми, якщо у

списку є однакові числа?

Візуалізація методу вибору

• Відкрийте вікно середовища створення та редагування проєктів https://samel.ho.ua/
• Уведіть змінений відповідно до умови задачі фрагмент проєкту для впорядкування списку методом вибору, наведений у тексті пункту. Коментарі вводити не потрібно.
• Збережіть проєкт у вашій папці у файлі з іменем вправа 3.3.1.py.
• Виконайте проєкт кілька разів з різними вхідними даними. Про аналізуйте результат його виконання.
• Закрийте вікно середовища створення проєктів

Задача. Створити проєкт для введення значень елементів списку і сортування його за незростанням методом вибору.

Працюємо з комп’ютером

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

Урок 12. СОРТУВАННЯ МЕТОДОМ ОБМІНУ. ПОШУК У СПИСКАХ ДАНИХ, ЯКІ ВІДПОВІДАЮТЬ ПЕВНИМ УМОВАМ

Готуємось до вивчення нового матеріалу

Матеріали для виконання

завдань, вправ та

файли-заготовки

• Які ви знаєте способи поміняти місцями значення двох змінних х та у?
• Для чого в опрацюванні списків використовується операція in?
• Для чого в опрацюванні списків використовуються методи count, index?