У сучасному світі програмування ми постійно працюємо з великими обсягами даних. Уміння швидко знайти потрібну інформацію або розставити її в правильному порядку — це база, на якій тримаються соціальні мережі, банківські системи та пошукові системи.
Сьогодні ми розберемо два критично важливі процеси: сортування (упорядкування) та бінарний пошук.
1. Упорядкування масиву: Метод «Бульбашки»
Найперше завдання розробника перед пошуком — привести дані до ладу. Найвідоміший навчальний алгоритм для цього — Bubble Sort (сортування бульбашкою).
Як це працює?
Алгоритм порівнює два сусідні елементи. Якщо лівий елемент більший за правий, вони міняються місцями. Таким чином, найбільші числа поступово «спливають» у кінець масиву, як бульбашки повітря у воді.
Приклад логіки на Python:
Python
# Початковий масив
numbers = [64, 34, 25, 12, 22, 11]
n = len(numbers)
# Алгоритм сортування
for i in range(n):
for j in range(0, n - i - 1):
if numbers[j] > numbers[j + 1]:
# Міняємо місцями
numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
print(f"Впорядкований масив: {numbers}")
2. Швидкий пошук: Бінарний алгоритм
Коли наш масив уже впорядкований (наприклад, від найменшого до найбільшого), нам не потрібно перевіряти кожне число підряд. Ми можемо використовувати бінарний пошук.
У чому його секрет?
Ми ділимо масив навпіл. Якщо шукане число більше за «серединне» — ми відкидаємо ліву половину масиву. Якщо менше — праву. Ми повторюємо це, поки не знайдемо потрібний елемент. Це у десятки разів швидше за звичайний перебір.
Приклад логіки:
- У масиві з 1000 елементів лінійний пошук може зробити 1000 кроків.
- Бінарний пошук знайде результат максимум за 10 кроків.
3. Етапи виконання практичної роботи
Щоб успішно виконати роботу, дотримуйтеся наступного плану дій:
- Створення даних: Згенеруйте масив із 10-15 випадкових чисел.
- Сортування: Реалізуйте цикл, який впорядкує ці числа за зростанням.
- Введення: Запитайте у користувача число, яке він хоче знайти.
- Пошук: Виконайте алгоритм бінарного пошуку.
- Фіналізація: Виведіть індекс знайденого числа або повідомлення, що такого числа немає.
Повний приклад програми
Ось готовий код, який поєднує всі етапи практичної роботи №11. Ви можете використовувати його як основу для свого проєкту.
Python
import random
# 1. Генеруємо масив випадкових чисел
data = [random.randint(1, 100) for _ in range(12)]
print(f"Початкові дані: {data}")
# 2. Сортування масиву (Бульбашка)
n = len(data)
for i in range(n):
for j in range(0, n - i - 1):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(f"Відсортовані дані: {data}")
# 3. Бінарний пошук
target = int(input("Яке число потрібно знайти? "))
low = 0
high = n - 1
found_index = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found_index = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
# 4. Виведення результату
if found_index != -1:
print(f"Число {target} знайдено! Його позиція в масиві: {found_index}")
else:
print(f"На жаль, числа {target} у списку немає.")
Висновок
Практична робота №11 демонструє, як математична логіка дозволяє оптимізувати роботу комп’ютера. Пам’ятайте: бінарний пошук неймовірно потужний, але він працює тільки тоді, коли ваші дані заздалегідь впорядковані.
Завдання для самоперевірки:
- Спробуйте змінити код сортування так, щоб масив впорядковувався за спаданням (від найбільшого до найменшого).
- Подумайте, чи буде працювати бінарний пошук, якщо в масиві є два однакові числа?
Успіхів у виконанні!