Перевірка по одному
Лінійний пошук: Перевірити кожен
Уявіть, що у вас є 10 карток обличчям вниз, пронумерованих від 1 до 10, перемішаних у випадковому порядку.
Ви хочете знайти карту з номером 7.
Ви переворачуєте карти одну за одною, зліва направо, доки не знайдете її.
| Сценарій | Потрібно перевернень |
|---|---|
| Найкращий випадок | 1 перевертання (щасливо з першої спроби!) |
| Найгірший випадок | 10 перевертань (вона була останньою карткою) |
| Середній | близько 5 перевертань |
Тепер уявіть 100 карток. Середній: близько 50 перевертань.
1000 карток? Середній: близько 500 перевертань.
Бачите закономірність? Подвійні карти, подвійна робота. Робота зростає по прямій лінії.
Комп'ютерні науковці називають це лінійним пошуком — лінійний означає, що робота зростає як лінія: стійко & передбачувано.
Лінійний пошук працює на БУДЬ-ЯКОМУ списку, відсортованому чи ні. Це робить його простим. Але він може стати повільним.
Скільки імен?
У вас є список класу з 20 імен, написаних у випадковому порядку.
Вам потрібно знайти ім'я Зоя.
Ви перевіряєте імена одне за одним, від верхньої частини списку вниз.
Розділити список навпіл
Двійковий пошук: Перейти до середини
Двійковий пошук має одне правило: список повинен бути спочатку відсортований.
Якщо ваш список з 20 імен йде від А до Я, ви можете використовувати двійковий пошук.
Як це працює: відкрийте на середньому імені (ім'я #10). Запитайте: Зоя раніше чи після цього імені?
Z знаходиться ближче до кінця алфавіту, тому Зоя приходить ПІСЛЯ середини. Викиньте першу половину. Тепер у вас залишилися тільки імена 11-20.
Перевірте середину тих 10 імен (ім'я #15). Z приходить після М, тому Зоя приходить після імені #15. Викиньте імена 11-14. Тепер у вас є імена 16-20.
Продовжуйте ділити навпіл. Кожна перевірка видаляє половину залишених імен.
| Розмір списку | Макс. перевірок з двійковим пошуком |
|---|---|
| 20 імен | максимум 5 перевірок |
| 1000 імен | максимум 10 перевірок |
| 1 000 000 імен | максимум 20 перевірок |
Порівняйте це з лінійним пошуком в 1 000 000 імен: середньо 500 000 перевірок.
Двійковий пошук розділяє список навпіл кожен раз. Повторне розділення навпіл дуже швидко досягає 1 — ось чому він залишається таким швидким.
Знайти 'fig' у відсортованому списку
Ось відсортований список 8 слів:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Ви хочете знайти fig за допомогою двійкового пошуку.
Пам'ятайте: перевірте середину, запитайте, чи ваша ціль приходить раніше чи після, потім розділіть список навпіл.
Обмін сусідів в порядку
Сортування бульбашками: Порівняти сусідів & Обміняти
Сортування бульбашками впорядковує список, порівнюючи два сусідні елементи за раз.
Якщо два сусіди не в порядку — обміняйте їх.
Продовжуйте робити проходи по списку, доки нічого не потрібно змінювати.
Приклад: сортування [5, 3, 8, 1]
Прохід 1:
- Порівняйте 5 & 3. 5 > 3, тому обміняйте → [3, 5, 8, 1]
- Порівняйте 5 & 8. 5 < 8, без обміну → [3, 5, 8, 1]
- Порівняйте 8 & 1. 8 > 1, тому обміняйте → [3, 5, 1, 8]
Прохід 2:
- Порівняйте 3 & 5. OK → [3, 5, 1, 8]
- Порівняйте 5 & 1. 5 > 1, обміняйте → [3, 1, 5, 8]
- Порівняйте 5 & 8. OK → [3, 1, 5, 8]
Прохід 3:
- Порівняйте 3 & 1. 3 > 1, обміняйте → [1, 3, 5, 8]
- Порівняйте 3 & 5. OK. Порівняйте 5 & 8. OK.
Готово! [1, 3, 5, 8] ✓
Зауважте: найбільше число піднімається до кінця списку на кожному проході. Ось як сортування бульбашками отримало свою назву.
Сортування бульбашками працює. Це не найшвидше для великих списків, але це легко зрозуміти — ідеально для навчання.
Сортування [4, 2, 7, 1] за допомогою сортування бульбашками
Відсортуйте цей список за допомогою сортування бульбашками: [4, 2, 7, 1]
Покажіть список після кожного проходу. Підрахуйте, скільки проходів потрібно, щоб закінчити.