Проверка по одному
Линейный поиск: проверка каждого
Представьте, что у вас есть 10 карточек, лежащих лицом вниз, с номерами от 1 до 10, перемешанные в случайном порядке.
Вы хотите найти карточку с номером 7.
Вы переворачиваете карточки по одной, слева направо, пока не найдёте её.
| Сценарий | Требуемые переворачивания |
|---|---|
| Лучший случай | 1 переворачивание (повезло с первой попытки!) |
| Худший случай | 10 переворачиваний (была последняя карточка) |
| В среднем | примерно 5 переворачиваний |
Теперь представьте 100 карточек. В среднем: примерно 50 переворачиваний.
1000 карточек? В среднем: примерно 500 переворачиваний.
Видите закономерность? Удвойте карточки, удвойте работу. Работа растёт по прямой линии.
Компьютерные учёные называют это линейным поиском — линейный означает, что работа растёт как линия: стабильная и предсказуемая.
Линейный поиск работает на ЛЮБОМ списке, отсортирован он или нет. Это делает его простым. Но он может быть медленным.
Сколько имён?
У вас есть список класса с 20 именами, написанными в случайном порядке.
Вам нужно найти имя Zoe.
Вы проверяете имена по одному, с начала списка вниз.
Разделите список пополам
Двоичный поиск: прыжок в середину
Двоичный поиск имеет одно правило: список должен быть отсортирован в первую очередь.
Если ваш список из 20 имён идёт от A до Z, вы можете использовать двоичный поиск.
Как это работает: откройте на среднее имя (имя #10). Спросите: идёт Zoe до или после этого имени?
Z идёт в конце алфавита, поэтому Zoe идёт ПОСЛЕ середины. Выбросьте первую половину. Теперь у вас остались только имена 11-20.
Проверьте середину из 10 имён (имя #15). Z идёт после M, поэтому Zoe идёт после имени #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. ОК → [3, 5, 1, 8]
- Сравните 5 и 1. 5 > 1, поменяйте → [3, 1, 5, 8]
- Сравните 5 и 8. ОК → [3, 1, 5, 8]
Проход 3:
- Сравните 3 и 1. 3 > 1, поменяйте → [1, 3, 5, 8]
- Сравните 3 и 5. ОК. Сравните 5 и 8. ОК.
Готово! [1, 3, 5, 8] ✓
Заметьте: наибольшее число всплывает в конец списка на каждом проходе. Вот как сортировка пузырьком получила своё название.
Сортировка пузырьком работает. Это не самый быстрый способ для больших списков, но это легко понять — идеально для обучения.
Отсортируйте [4, 2, 7, 1] методом сортировки пузырьком
Отсортируйте этот список, используя сортировку пузырьком: [4, 2, 7, 1]
Покажите список после каждого прохода. Сосчитайте, сколько проходов потребуется, чтобы закончить.