3.3. Сортування даних у списках. пошук у списках даних, які відповідають певним умовам

Зміст

ПРИГАДАЙТЕ

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

Набір даних вважається відсортованим, якщо значення кожного його наступного елемента відповідає певній умові відносно попереднього:

• За зростанням: значення кожного наступного елемента більше за значення попереднього (a[i+1] > a[i]).
• За спаданням: значення кожного наступного елемента менше за значення попереднього (a[i+1] < a[i]).
• За неспаданням: значення кожного наступного елемента не менше за значення попереднього (a[i+1] ≥ a[i]).
• За незростанням: значення кожного наступного елемента не більше за значення попереднього (a[i+1] ≤ a[i]).

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

Дані в таблицях Excel сортуються шляхом застосування команд впорядкування за зростанням або за спаданням до вибраного діапазону даних.

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

Відсортований набір даних кращий тим, що пошук потрібних значень у ньому відбувається значно швидше, ніж у невідсортованому.

ПРИГАДАЙТЕ

Як знайти найменше і найбільше значення у списку?

Найменше значення у списку можна знайти за допомогою функції min(), а найбільше — за допомогою функції max().

Як визначити індекс першого входження певного значення у список?

Індекс першого входження певного значення у список визначається за допомогою методу index().

ОБГОВОРІТЬ І ЗРОБІТЬ ВИСНОВКИ

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

Для сортування списку за спаданням методом вибору потрібно в умові порівняння змінити оператор менше (<) на оператор більше (>) у внутрішньому циклі, що шукає екстремальний елемент. У методі обміну (бульбашки) потрібно змінити умову if a[j] > a[j+1] на if a[j] < a[j+1].

2. Чи правильно сортуватимуть дані у списку вищенаведені проєкти, якщо список міститиме рівні між собою числа? Відповідь поясніть.

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

3. Перегляньте в інтернеті візуалізацію методу вибору, наприклад за адресами: https://www.youtube.com/watch?v=Ns4TPTC8whw або https://www.toptal.com/developers/sorting-algorithms.

Візуалізацію методу вибору переглянуто; вона демонструє, як на кожному кроці алгоритм знаходить мінімальний елемент у невідсортованій частині списку та ставить його на відповідну позицію.

ПОМІРКУЙТЕ

Чи правильно для обміну значеннями двох змінних x та y використати такі дві команди: x = y і y = x? Відповідь поясніть. Наведіть приклад.

Це неправильно. Після виконання першої команди (x = y) значення змінної x стає таким самим, як у y, а початкове значення x втрачається. Друга команда (y = x) просто присвоює y це нове значення x (яке вже дорівнює y), тому обидві змінні матимуть однакове значення, а початкове значення x не збережеться.

Приклад:
Нехай x = 5, y = 10.

1. x = y -> x стає 10, y залишається 10.
2. y = x -> y стає 10.
   Результат: x = 10, y = 10. Обмін не відбувся.

Яки ви знаєте способи поміняти місцями значення двох змінних x та y?

1. Використання допоміжної змінної:
   temp = x
x = y
y = temp
2. Використання можливостей мови Python (множинне присвоювання):
   x, y = y, x

ОБГОВОРІТЬ І ЗРОБІТЬ ВИСНОВКИ

1. Як змінити наведений проєкт, щоб він сортував списки за спаданням?

У проєкті з використанням методу обміну (сортування бульбашкою) потрібно змінити умову порівняння сусідніх елементів з if a[j] > a[j+1]: на if a[j] < a[j+1]:.

2. Чи правильно сортуватимуть дані у списку вищенаведені проєкти, якщо список міститиме рівні між собою числа? Відповідь поясніть.

Так, проєкти сортуватимуть дані правильно. Алгоритм порівнює елементи за допомогою оператора строгої нерівності (> або <), тому при наявності рівних чисел умова не виконується, вони залишаються на своїх місцях відносно одне одного, що не порушує загальний порядок сортування.

3. На яку одну команду можна замінити три останні команди циклу в наведеному проєкті?

Три останні команди циклу (використання допоміжної змінної x для обміну):
x = a[j]
a[j] = a[j+1]
a[j+1] = x

Можна замінити однією командою:
a[j], a[j+1] = a[j+1], a[j]

ПРИГАДАЙТЕ

4. В інтернеті можна подивитися візуалізацію методу обміну, наприклад за адресами: https://www.youtube.com/watch?v=lyZQPjUT5B4 або https://www.toptal.com/developers/sorting-algorithms.

Дане завдання є інформаційним та передбачає перегляд візуалізацій для кращого розуміння алгоритму сортування методом обміну (методом «бульбашки»).

Для чого в опрацюванні списків використовується операція in?

Операція in використовується для перевірки наявності або відсутності певних даних у списку.

Для чого в опрацюванні списків використовуються методи count, index?

Метод count використовується для визначення кількості входжень певного значення у список, а метод index — для визначення індексу першого входження певного значення у список.

ПОМІРКУЙТЕ

Від чого залежить швидкість знаходження потрібних даних?

Швидкість знаходження потрібних даних залежить від обсягу даних, способу їх організації (впорядкований чи невпорядкований список) та використаного алгоритму пошуку.

Наскільки важливо знайти потрібні дані якнайшвидше? Наведіть приклади.

Швидкий пошук є критично важливим для забезпечення ефективності роботи комп’ютерних систем та економії часу користувача. Прикладами є:

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

ПОМІРКУЙТЕ

Як змінити вищенаведений проєкт так, щоб у ньому не використовувалася змінна f?

Для виключення змінної f можна використати цикл for...else. Конструкція else після циклу for виконується лише тоді, коли цикл завершився природним шляхом, не зустрівши команду break.

a = [2, 4, 4, 6, 8, 10]
x = int(input())
for i in range(len(a)):
    if x < a[i]:
        a.insert(i, x)
        break
else:
    a.append(x)
print(a)

ПРАЦЮЄМО З КОМП’ЮТЕРОМ

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

a = list(map(float, input('Уведіть 6 чисел через пропуск > ').split()))
for i in range(len(a) - 1):
    nmax = i
    for j in range(i + 1, len(a)):
        if a[j] > a[nmax]:
            nmax = j
    a[i], a[nmax] = a[nmax], a[i]
print(a)

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

a = list(map(float, input('Уведіть 10 чисел через пропуск > ').split()))
for i in range(len(a) - 1):
    for j in range(len(a) - 1 - i):
        if a[j] < a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
print(a)

ДАЙТЕ ВІДПОВІДІ НА ЗАПИТАННЯ

1. Які ви знаєте методи сортування списку? Наведіть приклади.

Відомі методи сортування включають метод вибору та метод обміну (метод «бульбашки»). Прикладом використання стандартних методів Python є a.sort() та функція sorted(a).

2. З якою метою сортують списки?

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

ДАЙТЕ ВІДПОВІДІ НА ЗАПИТАННЯ

3. Яку ви знаєте функцію для сортування списку? Наведіть приклади їх використання.

Для сортування списку використовують метод sort() та функцію sorted().

Приклади використання:

• a.sort() — метод, що сортує список a на місці (початковий список змінюється).
• a.sort(reverse = True) — метод, що сортує список a за спаданням.
• b = sorted(a) — функція, що створює новий відсортований список b, зберігаючи початковий список a незмінним.
• b = sorted(a, reverse = True) — функція, що створює новий список b, відсортований за спаданням.

4. У чому полягає суть алгоритму сортування списку методом вибору?

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

5. У чому полягає суть алгоритму сортування списку методом обміну?

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

6. Як визначити, чи є потрібне значення у списку?

Визначити наявність або відсутність значення у списку можна за допомогою операції in. Наприклад: if x in a:.

7. Як визначити, скільки разів трапляється потрібне значення у списку?

Визначити кількість входжень значення у список можна за допомогою методу count(). Наприклад: n = a.count(x).

ОБГОВОРІТЬ І ЗРОБІТЬ ВИСНОВКИ

1. Чим відрізняються результати метода sort і функції sorted упорядкування списку?

Метод sort змінює початковий список, впорядковуючи його елементи, тоді як функція sorted створює новий відсортований список, залишаючи початковий список без змін.

2. У яких випадках зручніше використовувати метод sort, а в яких — функцію sorted?

Метод sort зручніше використовувати, коли потрібно відсортувати наявний список і немає потреби зберігати його початковий, невпорядкований стан. Функцію sorted зручніше використовувати тоді, коли необхідно отримати впорядковану копію даних, зберігши при цьому початковий список для подальшого використання.

ВИКОНАЙТЕ ЗАВДАННЯ

1. У списку зберігаються оцінки з інформатики групи учнів / учениць. Відсортуйте цей список за спаданням і визначте, скільки учнів / учениць мають найнижчу в цій групі оцінку. Збережіть проєкт у вашій папці у файлі з іменем завдання 3.3.1.

# Завдання 3.3.1
grades = [8, 10, 7, 12, 7, 9, 10, 7]
grades.sort(reverse=True) # Сортування за спаданням
min_grade = grades[-1] # Останній елемент — найнижча оцінка
count = grades.count(min_grade)
print(f"Кількість учнів з найнижчою оцінкою: {count}")

2. У даному відсортованому списку визначте, яке число трапляється в ньому найбільшу кількість разів. Збережіть проєкт у вашій папці у файлі з іменем завдання 3.3.2.

# Завдання 3.3.2
# Нехай маємо відсортований список a
a = [1, 2, 2, 3, 3, 3, 4, 5]
most_frequent = a[0]
max_count = 0

for x in set(a):
    current_count = a.count(x)
    if current_count > max_count:
        max_count = current_count
        most_frequent = x

print(f"Число, що трапляється найчастіше: {most_frequent}")

3. Є відсортований список. Визначте, скільки в ньому різних значень. Наприклад, у списку [1, 2, 4, 1, 2] різних значень 3. Збережіть проєкт у вашій папці у файлі з іменем завдання 3.3.3.

# Завдання 3.3.3
a = [1, 1, 2, 2, 4]
different_values_count = len(set(a))
print(f"Кількість різних значень: {different_values_count}")

ВИКОНАЙТЕ ЗАВДАННЯ

4. У спортивних змаганнях з бігу на 100 м взяли участь 20 учасників. Розташуйте прізвища учасників змагання за зростанням їхнього часу бігу. Використайте два списки — для зберігання прізвищ і для зберігання результатів. Збережіть проєкт у вашій папці у файлі з іменем завдання 3.3.4.

# Прізвища учасників та їхні результати (приклад даних)
names = ["Петренко", "Сидоренко", "Іваненко", ...] # Список з 20 прізвищ
times = [12.5, 11.8, 13.2, ...] # Список з 20 результатів часу

# Сортування обох списків залежно від значень у times
# Використовуємо метод об'єднання в пари, сортування та розділення
combined = sorted(zip(times, names))
times, names = zip(*combined)

print("Список учасників за зростанням часу:")
for i in range(len(names)):
    print(f"{names[i]}: {times[i]} с")

5. Змініть проєкт упорядкування списку методом обміну, щоб його виконання переривалося, якщо після чергового проходження списку жодного обміну не відбулося. Збережіть проєкт у вашій папці у файлі з іменем завдання 3.3.5.

a = [13, 6, 5, 18, 11, 10]
n = len(a)
for i in range(n):
    swapped = False
    for j in range(0, n - i - 1):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swapped = True
    if not swapped:
        break
print(a)

6. Змініть проєкт упорядкування списку методом вибору, щоб обмін найменшого значення і першого значення з поки що не впорядкованої частини списку відбувався лише тоді, коли це доцільно робити. Збережіть проєкт у вашій папці у файлі з іменем завдання 3.3.6.

a = [23, 7, 4, 16, -2, 10]
for i in range(len(a)):
    min_index = i
    for j in range(i + 1, len(a)):
        if a[j] < a[min_index]:
            min_index = j
    # Обмін відбувається тільки якщо знайдено елемент менший за поточний
    if min_index != i:
        a[i], a[min_index] = a[min_index], a[i]
print(a)

7. Створіть власну візуалізацію одного з методів упорядкування списку (анімовану презентацію, відеофільм або інше).

[!NOTE]
Промпт для створення зображення:
A clear and educational infographic titled ‘Метод бульбашки’ (Bubble Sort) in Ukrainian, showing a row of colorful boxes with numbers inside. Arrows indicate the process of swapping adjacent boxes where the left one is larger than the right one. The design should be clean, vector-style, suitable for a school presentation.

1. Пригадайте, де у проєктах ви використовували тексти.

Тексти у проєктах використовувалися для виведення повідомлень користувачеві (функція print), введення даних (функція input), збереження імен учасників, паролів, назв товарів та інших текстових міток.

ГОТУЄМОСЬ ДО ВИВЧЕННЯ НОВОГО МАТЕРІАЛУ

2. Як перевести текстове подання в число і число в його текстове подання? Де ви це використовували?

Для переведення текстового подання в число використовується функція float() або int(), а для переведення числа в текстове подання — функція str(). Ці функції використовувалися при введенні даних з клавіатури за допомогою функції input(), де введені значення спочатку є текстовими, та при виведенні результатів обчислень, коли числа потрібно об’єднати з текстом для відображення.