- Сравниваются
- Обменяны
- На месте
Сортировка пузырьком
Сортировка пузырьком снова и снова проходит по списку, сравнивает каждую пару соседей и меняет их местами, если левый больше. После каждого прохода наибольшее значение, которое ещё не на месте, «всплывает» в конец. Запустите сортировку с любой скоростью или пройдите её по одному сравнению и следите за счётчиками сравнений, обменов и проходов. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Плитки считают сравнения, обмены и проходы. Выберите число столбиков, начальный порядок или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
- Следите, как плитки считают сравнения, обмены и проходы, и сравните их с худшим случаем.
Как работает сортировка пузырьком
Начните слева. Сравните первые два значения; если левое больше, поменяйте их местами. Сдвиньтесь на одно место вправо и снова сравните, и так до конца списка. Это один проход, и после него наибольшее значение стоит на последнем месте. Следующий проход заканчивается на одно место раньше. Продолжайте, пока проход не обойдётся без обменов или не останется одно значение.
Сколько работы
Для n значений первый проход делает n − 1 сравнений, следующий n − 2 и так далее, поэтому полная сортировка делает не более n(n − 1)/2 сравнений. Число обменов всегда равно числу инверсий в начальном списке — пар значений, стоящих в неправильном порядке. Больше всего их у обратного списка: n(n − 1)/2. У отсортированного их нет, и с ранней остановкой ему хватает одного прохода из n − 1 сравнений.
Часто задаваемые вопросы
Почему она называется сортировкой пузырьком?
Потому что большие значения поднимаются к концу списка, как пузырьки в воде. В каждом проходе наибольшее значение, которое ещё не на месте, шаг за шагом движется вправо, пока не займёт своё окончательное место.
Сколько сравнений и обменов делает сортировка пузырьком?
Не более n(n − 1)/2 сравнений для n значений: 45 для 10 значений, 780 для 40. Число обменов всегда равно числу инверсий в начальном списке: от нуля для отсортированного списка до n(n − 1)/2 для обратного.
Что даёт ранняя остановка?
Если за весь проход не было ни одного обмена, все соседи стоят по порядку, значит, список отсортирован и можно остановиться. С ранней остановкой отсортированному списку хватает одного прохода. Без неё сортировка пузырьком всегда делает все n − 1 проходов.
Используется ли сортировка пузырьком на практике?
Редко. Она простая и устойчивая, но в среднем работает за время, пропорциональное n². Сортировка вставками делает то же за меньшее число шагов на коротких или почти отсортированных списках, а сортировка слиянием и быстрая сортировка намного быстрее на длинных.
Мои числа куда-то отправляются?
Нет. Сортировка работает в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор