Складання і виконання алгоритму упорядкування та пошуку значень у масиві

Тема: Алгоритми сортування та пошуку в масиві

Мета: Навчитися впорядковувати масиви та шукати в них значення за допомогою алгоритмів сортування і пошуку.

Хід роботи:

1. Створення масиву.
   Написати програму, яка генерує випадковий список цілих чисел (наприклад, від 1 до 100) довжиною N, де N вводить користувач.

2. Сортування масиву.
   Реалізувати один із методів сортування (наприклад, бульбашкове сортування або сортування вибором).

3. Пошук у масиві.
   Реалізувати два способи пошуку:

   • Лінійний пошук (перевіряє кожен елемент послідовно).

   • Бінарний пошук (працює тільки на відсортованих масивах).

4. Перевірка роботи.

   • Вивести початковий та відсортований масиви.

   • Запросити у користувача число для пошуку.

   • Вивести, чи є число в масиві, та його індекс (або повідомити, що його немає).

Введіть розмір масиву: 10

Початковий масив: [45, 23, 78, 10, 89, 54, 32, 11, 67, 91]

Відсортований масив: [10, 11, 23, 32, 45, 54, 67, 78, 89, 91]

Введіть число для пошуку: 32

Лінійний пошук: Число 32 знайдено на позиції 3

Бінарний пошук: Число 32 знайдено на позиції 3

Що таке бінарний пошук?
Бінарний пошук – це ефективний алгоритм пошуку елемента в відсортованому масиві. Він працює за принципом "розділяй і володарюй", що дозволяє швидко знаходити потрібний елемент, зменшуючи діапазон пошуку вдвічі на кожному кроці.

Як працює бінарний пошук?

1. Беремо середній елемент масиву.

2. Порівнюємо його з шуканим значенням:

   • Якщо співпав – готово! 🎯

   • Якщо менший – шукаємо в правій половині.

   • Якщо більший – шукаємо в лівій половині.

3. Повторюємо кроки 1-2, поки не знайдемо елемент або не залишиться частин для пошуку.

Приклад на простих числах

Припустимо, у нас є масив:
[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Хочемо знайти число 23.

✅ 1. Беремо середній елемент → 16 (посередині).

• 23 більше за 16 → шукаємо в правій половині [23, 38, 56, 72, 91].

✅ 2. Беремо середину цієї частини → 56.

• 23 менше за 56 → шукаємо в лівій половині [23, 38].

✅ 3. Беремо середній → 38.

• 23 менше за 38 → залишився тільки [23].

✅ 4. Ось він! 🎉 Число знайдено!

Переваги бінарного пошуку

🚀 Швидкість – працює за O(log n), що набагато ефективніше за звичайний пошук O(n).
📉 Менше порівнянь – порівнюємо не кожен елемент, а тільки логарифмічну кількість разів.

❗ ВАЖЛИВО – бінарний пошук працює тільки на відсортованих масивах!

🔹 Досі не зрозуміло?

Лінійний пошук (Linear Search) – пояснення простими словами

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

Як працює лінійний пошук?

1. Беремо перший елемент масиву.

2. Порівнюємо його з шуканим значенням:

   • Якщо співпав – вітаю! 🎉 Ми його знайшли.

   • Якщо ні – переходимо до наступного.

3. Продовжуємо цей процес, поки не знайдемо значення або не переглянемо весь список.

Приклад на простих числах

Припустимо, у нас є масив:
[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Хочемо знайти число 23.

✅ 1. Порівнюємо з 2 – не підходить.
✅ 2. Порівнюємо з 5 – не підходить.
✅ 3. Порівнюємо з 8 – не підходить.
✅ 4. Порівнюємо з 12 – не підходить.
✅ 5. Порівнюємо з 16 – не підходить.
✅ 6. Порівнюємо з 23 – 🎉 Знайшли!

Переваги та недоліки

✔ Працює на будь-якому списку (не потрібно сортувати).
✔ Простий у реалізації – можна написати за кілька рядків коду.
❌ Повільний для великих масивів – працює за O(n), тобто в гіршому випадку доведеться перевірити всі n елементів.

Лінійний пошук vs. Бінарний пошук

💡 Підсумок:
Лінійний пошук – це метод "йти по порядку, доки не знайдемо". Простий, але може бути повільним, якщо елементів багато.

Сортування бульбашкою (Bubble Sort) – просте пояснення

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

Як працює сортування бульбашкою?

1. Переглядаємо масив зліва направо.

2. Порівнюємо два сусідні елементи.

   • Якщо лівий більший за правий → міняємо місцями.

   • Якщо ні → залишаємо як є.

3. Продовжуємо так до кінця масиву → найбільший елемент опиняється в кінці.

4. Повторюємо процес для решти елементів, ігноруючи вже відсортовані частини.

5. Закінчуємо, коли не було жодної заміни (масив відсортований).

Приклад сортування бульбашкою

🔢 Початковий масив:

[5, 3, 8, 4, 2]

🔄 1-й прохід:

• (5, 3) → 5 > 3 → 🔄 міняємо → [3, 5, 8, 4, 2]

• (5, 8) → 5 < 8 → ✅ залишаємо

• (8, 4) → 8 > 4 → 🔄 міняємо → [3, 5, 4, 8, 2]

• (8, 2) → 8 > 2 → 🔄 міняємо → [3, 5, 4, 2, 8]

🔄 2-й прохід:

• (3, 5) → 3 < 5 → ✅ залишаємо

• (5, 4) → 5 > 4 → 🔄 міняємо → [3, 4, 5, 2, 8]

• (5, 2) → 5 > 2 → 🔄 міняємо → [3, 4, 2, 5, 8]

• (5, 8) → ✅ залишаємо

🔄 3-й прохід:

• (3, 4) → ✅ залишаємо

• (4, 2) → 4 > 2 → 🔄 міняємо → [3, 2, 4, 5, 8]

🔄 4-й прохід:

• (3, 2) → 3 > 2 → 🔄 міняємо → [2, 3, 4, 5, 8]

📌 Масив відсортований! 🎉

Часова складність

• ❌ Найгірший випадок: O(n²) (коли масив повністю не відсортований)

• ✅ Найкращий випадок: O(n) (якщо масив уже відсортований)

• ⚠️ Працює повільно для великих масивів, але дуже простий у реалізації.

Коли використовувати?

✅ Коли масив маленький.
✅ Коли треба простий алгоритм для навчання.
❌ Не підходить для великих даних – краще використовувати швидке сортування (QuickSort) або сортування злиттям (MergeSort).