Сортировка пузырьком
Сортировка пузырьком — интерактивный эксперимент из приложения «Алгоритмы в действии», бесплатной симуляции StudyFi Lab, которая работает прямо в браузере.
Сортировка пузырьком сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке. После каждого прохода самый большой элемент «всплывает» в конец, и неотсортированная часть становится короче. Если за проход не было ни одного обмена, массив отсортирован. В худшем случае нужно n(n−1)/2 сравнений, то есть O(n²).
Попробуй: Выбери обратный порядок и сравни число сравнений с n(n−1)/2. Затем попробуй почти отсортированный массив — он закончится через пару проходов.
Частые вопросы
Что показывает эксперимент «Сортировка пузырьком»?
Сортировка пузырьком сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке. После каждого прохода самый большой элемент «всплывает» в конец, и неотсортированная часть становится короче. Если за проход не было ни одного обмена, массив отсортирован. В худшем случае нужно n(n−1)/2 сравнений, то есть O(n²).
Как попробовать «Сортировка пузырьком»?
Выбери обратный порядок и сравни число сравнений с n(n−1)/2. Затем попробуй почти отсортированный массив — он закончится через пару проходов.
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.