Перевірка одного за одним
Лінійне Шукання: Перевірка кожної
Вимагайте, що ви маєте 10 карток, з яких 10 з обох боків, з номерами від 1 до 10, перемішаними в випадковому порядку.
Ви хочете знайти картку з номером 7.
Ви перевернуваєте картки одну за одною, зліва направо, поки не знайдете її.
| Сценарій | Потреба у переворотах |
|----------|-------------|
| Найкращий випадок | 1 переворот (щасливий перший спроба!) |
| Найгірший випадок | 10 переворотів (вона була останньою карткою) |
| Середній | близько 5 переворотів |
Тепер уявіть 100 карток. Середній: близько 50 переворотів.
1000 карток? Середній: близько 500 переворотів.
Видите патерн? Двічі збільшити кількість карток, двічі збільшити роботу. Робота зростає в прямій лінії.
Комп'ютерні вчені називають це лінійне шукання — лінійне означає, що робота зростає як лінія: стабільна та передбачувана.
Лінійне шукання працює на будь-якій послідовності, відсортованій чи ні. Це робить його простим. Але він може стати повільним.
Скільки імен?
Ви маєте список класу з 20 іменами написаними в випадковому порядку.
Вам потрібно знайти ім'я Zoe.
Ви перевіряєте імена одну за одною, згори донизу.
Розділіть список наполовину
Двоична пошук: стрибніть до середини
Двоична пошук має одну правило: перший список повинен бути відсортованим.
Якщо ваш список з 20 імен від A до Z, ви можете використовувати двоичну пошук.
Як це працює: відкрийте до середнього імені (імя #10). Спитайте: чи знаходиться Зої перед цим іменем?
З з'являється наприкінці алфавіту, тому Зої знаходиться ПІСЛЯ середини. Відкиньте першу половину. Тепер у вас залишається лише імена 11-20.
Переконайтеся, що серед тих 10 імен (імя #15). З з'являється після M, тому Зої знаходиться після іміні #15. Відкиньте імена 11-14. Тепер у вас залишаються імена 16-20.
Постійно розділяйте наполовину. Кожен перегляд видаляє половину залишкових імен.
Список розміру | Максимальне кількість перевірок з двоичною пошукою |
|-----------|-------------------------------|
| 20 імен | не більше 5 перевірок |
| 1,000 імен | не більше 10 перевірок |
| 1,000,000 імен | не більше 20 перевірок |
Порівняйте з лінійною пошуком на 1,000,000 імен: середня кількість 500,000 перевірок.
Двоична пошук розділяє список наполовину кожен раз. Розділяти наполовину повторно досягає 1 дуже швидко - це й причина, чому вона залишається дуже швидкою.
Знайдіть 'fig' у відсортованому списку
Ви можете побачити відсортований список з 8 слів:
1. яблуко 2. банан 3. вишня 4. дату 5. липа 6. fig 7. виноград 8. медонос
Ви хочете знайти fig за допомогою двоичної пошук.
Пам'ятайте: перевіряйте середину, спитайте, чи ваша мета знаходиться перед або після, а потім розділіть список наполовину.
Обмін сусідами в порядку
Підрядне сортування: порівняння сусідів та обмін
Bubble sort puts a list in order by comparing two neighboring items at a time.
If two neighbors are out of order — swap them.
Keep making passes through the list until nothing needs swapping.
Example: sort [5, 3, 8, 1]
Pass 1:
- Compare 5 & 3. 5 > 3, so swap → [3, 5, 8, 1]
- Compare 5 & 8. 5 < 8, no swap → [3, 5, 8, 1]
- Compare 8 & 1. 8 > 1, so swap → [3, 5, 1, 8]
Pass 2:
- Compare 3 & 5. OK → [3, 5, 1, 8]
- Compare 5 & 1. 5 > 1, swap → [3, 1, 5, 8]
- Compare 5 & 8. OK → [3, 1, 5, 8]
Pass 3:
- Compare 3 & 1. 3 > 1, swap → [1, 3, 5, 8]
- Compare 3 & 5. OK. Compare 5 & 8. OK.
Done! [1, 3, 5, 8] ✓
Notice: the biggest number bubbles to the end of the list on each pass. That is how bubble sort gets its name.
Bubble sort works. It is not the fastest for big lists, but it is easy to understand — perfect for learning.
Sort [4, 2, 7, 1] with Bubble Sort
Sort this list using bubble sort: [4, 2, 7, 1]
Show the list after each pass. Count how many passes it takes to finish.