Сортировка и поиск данных
Линейный и бинарный поиск, сортировка пузырьком по шагам: сколько сравнений нужно и почему сначала данные приводят в порядок.
В алфавитном словаре слово «молоко» ты найдёшь за десять секунд. В куче неразобранных тетрадей — никогда: придётся перерыть всё. Разница не в тебе, а в порядке данных. Компьютер живёт по тем же правилам: массив из миллиона чисел можно искать долго, а можно за мгновение — смотря подготовлен ли он. Сначала поговорим про поиск, потом про то, как этот порядок навести.
Поиск — самая частая операция компьютера: набрал слово в поиске, нашёл контакт в телефоне, открыл товар по названию. Каждый раз где-то в памяти машины работает алгоритм поиска — и от того, какой именно, зависит, ответит система за мгновение или задумается на секунды. Для школьных массивов в десяток элементов подойдёт любой метод. Но настоящие базы данных хранят миллионы записей, и там выбор алгоритма — это разница между мгновением и минутой ожидания.
Линейный и бинарный поиск
Линейный поиск честный, но медленный: берёшь элементы по одному и сравниваешь, пока не найдёшь. В худшем случае — n сравнений, для миллиона элементов — миллион. Бинарный поиск работает только с отсортированными данными: смотришь в середину, сравниваешь и выбрасываешь половину массива. Ищем 19 в списке 2, 5, 8, 11, 15, 19, 22: середина 11, значит 19 правее — остаются 15, 19, 22; новая середина 19 — нашли. Два шага вместо шести. Для массива из n элементов хватит делений: миллиард элементов — около 30.
- Массив 2, 5, 8, 11, 15, 19, 22. Середина — 11. Число 19 больше, берём правую половину.
- Остались 15, 19, 22. Середина — 19. Совпало.
- Готово: два шага вместо шести сравнений.
В программе бинарный поиск выглядит так: две границы, левая и правая, охватывают рабочий диапазон. Середина считается как mid = (left + right) // 2, затем искомое число сравнивают с элементом середины: меньше — переносим правую границу, больше — левую, равно — нашли. Границы сближаются с каждым шагом, а если они пересеклись, значит элемента в массиве нет. Главная аккуратность — сдвигать границу за середину, а не на неё саму, иначе на двух элементах поиск может зациклиться.
Почему деление пополам — это быстро
Каждый шаг бинарного поиска режет диапазон вдвое, поэтому число шагов растёт страшно медленно: тысяча элементов — 10 шагов, миллион — 20, миллиард — 30. Сравни с линейным поиском: там шагов n, и для миллиарда записей это миллиард сравнений. Разница между 20 и 1 000 000 000 — вот что скрывается за фразой «алгоритмы бывают быстрые и медленные». База данных магазина с миллионами товаров отвечает на запрос за миллисекунды именно потому, что данные заранее отсортированы и поиск идёт делением пополам.
| Элементов (n) | Шагов бинарного поиска | Сравнений пузырька (примерно) |
|---|---|---|
| 10 | 4 | 45 |
| 1 000 | 10 | около 500 000 |
| 1 000 000 | 20 | сотни миллиардов |
Сортировка пузырьком
Чтобы бинарный поиск заработал, данные надо отсортировать. Простейший способ — пузырёк: идёшь по массиву, сравниваешь соседей и меняешь местами, если они стоят неправильно. Самое большое число за проход «всплывает» в конец, как пузырёк воздуха. Массив 5, 3, 8, 1 сортируется за три прохода. В Python один шаг обмена записывают так: if nums[i] > nums[i+1]: nums[i], nums[i+1] = nums[i+1], nums[i].
Пузырёк по шагам: полный прогон
- Первый проход, пара 5 и 3: стоят неправильно, меняем — массив 3, 5, 8, 1.
- Пара 5 и 8: порядок верный, обмен не нужен.
- Пара 8 и 1: неправильно, меняем — после первого прохода массив 3, 5, 1, 8. Восьмёрка всплыла в конец.
- Второй проход: пара 3 и 5 в порядке, пара 5 и 1 даёт обмен — массив 3, 1, 5, 8.
- Третий проход: обмен 3 и 1 — массив 1, 3, 5, 8. Отсортировано за три прохода.
| Проход пузырька | Массив после прохода |
|---|---|
| 1 | 3, 5, 1, 8 |
| 2 | 3, 1, 5, 8 |
| 3 | 1, 3, 5, 8 |
Отсюда гарантия пузырька: за один проход самый большой элемент точно встаёт на последнее место, за второй — предпоследнее, и так далее. После i проходов последние i элементов уже на своих местах, и их можно не трогать. На этом основано точное число сравнений: n - 1 в первом проходе, n - 2 во втором и так далее до единицы — для больших n счёт растёт как n в квадрате.
Проверь гарантию на нашем массиве: после первого прохода 3, 5, 1, 8 — восьмёрка в конце, и дальше она не двигается. После второго прохода 3, 1, 5, 8 — пятёрка тоже пристроилась. Осталось упорядочить только пару 3 и 1, и третий проход сделает это одним обменом. Каждый проход работает со всё более коротким начальным куском массива.
Сколько действий: квадрат против логарифма
Сведём методы в одну таблицу. Для маленьких списков все методы работают мгновенно, и разницы не видно. Но при тысячах элементов пузырёк проигрывает в тысячи раз, а при миллионах — в сотни тысяч. Поэтому на больших данных пузырёк живёт разве что в учебных задачах, а в реальных системах работают быстрые методы вроде быстрой сортировки: они тоже сравнивают и обменивают элементы, но режут массив на части вместо последовательного перебора.
Умный пузырёк и сортировка выбором
У пузырька есть бесплатная оптимизация: если за проход не случилось ни одного обмена, массив уже отсортирован, и работу можно прекращать. Для почти упорядоченных данных это сокращает число проходов с n - 1 до двух-трёх. Другой простой метод — сортировка выбором: пройди по массиву, найди минимум, поставь его на первое место, затем ищи минимум в остатке и ставь на второе. Обменов у выбором меньше, чем у пузырька, а идея такая же — медленно, зато прозрачно. В Python есть готовый sorted(nums) и метод nums.sort(), но на уроках сортировку пишут руками, чтобы механизм увидеть своими глазами.
Сортировка вокруг нас
- Список контактов в телефоне упорядочен по алфавиту — иначе пришлось бы листать тысячи имён
- Магазин сортирует товары по цене и рейтингу — на отсортированных данных поиск дешёвого мгновенный
- Результаты забега выводят по времени финиша — от меньшего к большему
- Поисковик ранжирует сайты по релевантности — это тоже сортировка, только не по алфавиту
- Проводник файлов сортирует папки по имени или дате — режим на выбор
Заметь закономерность: почти всё, чем ты пользуешься каждый день, заранее отсортировано. Порядок наводят один раз, а выигрывают при каждом поиске — экономия копится с каждым запросом. Это общий принцип информатики: подготовка данных стоит дороже одного запроса, но окупается на миллионах запросов.
- Линейный поиск#
- перебор элементов по одному до совпадения
- Бинарный поиск#
- поиск по отсортированным данным: сравнение с серединой и отбрасывание половины
- Сортировка#
- расстановка данных по возрастанию или убыванию
- Проход#
- один обход массива со сравнением соседних пар
- Обмен#
- перестановка двух соседних элементов местами
- Массив#
- упорядоченный набор элементов, доступных по индексу
Как это спрашивают: обратные задачи
На ОГЭ сортировка встречается в двух ролях: посчитать количество сравнений или обменов в маленьком массиве и проследить, как массив выглядит после нескольких проходов. Обе решаются честным прогоном на бумаге — массивы там маленькие, по пять-шесть элементов. Не угадывай: две минуты прогона надёжнее любой интуиции.
- Задача 1: отсортированный массив из 200 элементов ищут бинарным поиском. Сколько шагов в худшем случае?
- Подбираем степень двойки: 2 в седьмой — 128, мало; 2 в восьмой — 256, хватает. Ответ: 8 шагов.
- Задача 2: массив 4, 2, 7, 1 сортируют пузырьком. Как он выглядит после двух проходов?
- Первый проход: обмен 4 и 2, затем обмен 7 и 1 — получается 2, 4, 1, 7.
- Второй проход: обмен 4 и 1 — получается 2, 1, 4, 7. Семёрка и четвёрка уже на своих местах.
Бинарный поиск требует отсортированных данных и на каждом шаге делит диапазон , а пузырёк сравнивает элементы и меняет их местами
Банк слов
Проверь себя
Клавиши 1–9 выбирают вариант, Enter — «Проверить»
1 Что выведет программа? nums = [3, 1]; если nums[0] больше nums[1], обменять их местами; print(nums[0], nums[1]). Впиши два числа через пробел.
2 Какой поиск требует, чтобы данные были заранее отсортированы?
3 Массив из 1024 элементов отсортирован. Сколько шагов займёт бинарный поиск в худшем случае?
4 Сортировка пузырьком сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке.
5 Соедини метод с его характеристикой.
Нажми на элемент слева, затем на его пару справа. Повторное нажатие отменяет связь.
6 В неотсортированном массиве из 100 элементов ищут число 77 линейным поиском, и оно стоит последним. Сколько сравнений сделает поиск?
7 Как ищут?
Разложи элементы по категориям: нажми на элемент, потом на категорию.
8 Вставь пропущенное.
Выбери подходящее слово в каждом пропуске.
Бинарный поиск на каждом шаге делит диапазон , поэтому для 1024 отсортированных элементов хватает шагов
Было понятно? Скажи — так мы видим, какие темы переписать.
Частые вопросы
Почему бинарный поиск нельзя применять к неотсортированным данным?
Он сравнивает искомое число с серединой и отбрасывает половину массива. Без порядка нельзя понять, в какой половине продолжать поиск.
Почему пузырёк называют медленным?
На массиве из n элементов он делает до n-1 проходов по n-1 сравнению — порядка n в квадрате действий. Для миллиона элементов это триллионы операций, поэтому для больших данных придуманы быстрые сортировки.
Как быстро оценить число шагов бинарного поиска?
Подбери степень двойки: 2^7 = 128, значит в списке из 100 элементов хватит 7 шагов. Для тысячи элементов — 10 шагов, а для миллиарда — около 30: деление пополам дорожает медленно.
Какой сортировкой пользуются в реальных программах?
Не пузырьком: в стандартных библиотеках работают быстрые методы, которые делят массив на части и делают порядка n умножить на log n сравнений. Пузырёк остаётся учебным — на нём хорошо виден сам механизм обменов.