Алгоритмы в действии
Алгоритмы в действии — бесплатная интерактивная симуляция из StudyFi Lab. Работает прямо в браузере, без регистрации и установки.
Сортировка и поиск шаг за шагом
Эксперименты
Сортировка пузырьком
Сортировка пузырьком сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке. После каждого прохода самый большой элемент «всплывает» в конец, и неотсортированная часть становится короче. Если за проход не было ни одного обмена, массив отсортирован. В худшем случае нужно n(n−1)/2 сравнений, то есть O(n²).
Попробуй: Выбери обратный порядок и сравни число сравнений с n(n−1)/2. Затем попробуй почти отсортированный массив — он закончится через пару проходов.
Сортировка вставками
Сортировка вставками похожа на упорядочивание карт в руке: левая часть уже отсортирована, а каждый следующий элемент (key) сдвигается влево, пока не встретит меньший. Большие элементы при этом сдвигаются на одно место вправо. На случайных данных это O(n²), а на почти отсортированных — почти O(n): отсортированному массиву нужно всего n−1 сравнений.
Попробуй: Запусти её на почти отсортированном массиве, а затем на обратном. Во сколько раз больше сдвигов нужно обратному?
Сортировка слиянием
Сортировка слиянием делит массив пополам, сортирует каждую половину тем же способом (рекурсия), а затем сливает две отсортированные половины: всегда берёт меньший из двух первых элементов. Деление пополам даёт log₂ n уровней, и на каждом уровне обрабатываются все n элементов, поэтому время всегда O(n log n). При равенстве берётся левый элемент, поэтому сортировка устойчива.
Попробуй: Попробуй обратный, а затем почти отсортированный массив того же размера. Число сравнений почти не меняется — порядок входных данных почти не важен.
Быстрая сортировка
Быстрая сортировка выбирает опорный элемент — здесь последний элемент отрезка (разбиение Ломуто) — и переставляет отрезок так, чтобы меньшие элементы оказались слева, а остальные справа. Опорный элемент встаёт на своё окончательное место, а обе части сортируются так же. В среднем это O(n log n), но если опорный элемент делит плохо (например, на уже отсортированном или обратном массиве), время падает до O(n²).
Попробуй: Сравни случайный вход с обратным. На обратном массиве опорный элемент всегда наибольший или наименьший — посмотри, как подскочит число сравнений.
Линейный и двоичный поиск
Линейный поиск проверяет элементы по одному, поэтому в худшем случае ему нужно n шагов — O(n). Двоичный поиск работает только на отсортированном массиве: он смотрит в середину и по результату отбрасывает целую половину. После каждого шага остаётся не больше половины, поэтому хватает не более ⌈log₂(n+1)⌉ шагов — O(log n). Для 40 элементов это 6 шагов вместо 40.
Попробуй: Задай 40 элементов и ищи последнее значение. Затем выбери число, которого нет в массиве, — сколько шагов нужно каждому поиску, чтобы это понять?
Гонка сортировок
Все четыре алгоритма сортируют одинаковые данные, и на каждой дорожке один шаг — это одно сравнение или одно перемещение. Алгоритмы O(n²) (пузырьком и вставками) растут с размером массива гораздо быстрее, чем O(n log n) (слиянием и быстрая). Но порядок зависит и от входа: на почти отсортированном массиве часто побеждает сортировка вставками.
Попробуй: Запусти гонку на случайном массиве из 40 элементов, затем переключись на почти отсортированный. Сменится ли победитель?
Частые вопросы
Что такое «Алгоритмы в действии»?
Алгоритмы в действии — бесплатная интерактивная симуляция из StudyFi Lab. Работает прямо в браузере, без регистрации и установки. Сортировка и поиск шаг за шагом
Приложение «Алгоритмы в действии» бесплатное?
Да. Приложение «Алгоритмы в действии» полностью бесплатное. Оно работает в браузере на компьютере, планшете и телефоне, аккаунт не нужен.
Что можно изучить в приложении «Алгоритмы в действии»?
Сортировка пузырьком, Сортировка вставками, Сортировка слиянием, Быстрая сортировка, Линейный и двоичный поиск, Гонка сортировок.
Что показывает эксперимент «Сортировка пузырьком»?
Сортировка пузырьком сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке. После каждого прохода самый большой элемент «всплывает» в конец, и неотсортированная часть становится короче. Если за проход не было ни одного обмена, массив отсортирован. В худшем случае нужно n(n−1)/2 сравнений, то есть O(n²).
Что показывает эксперимент «Сортировка вставками»?
Сортировка вставками похожа на упорядочивание карт в руке: левая часть уже отсортирована, а каждый следующий элемент (key) сдвигается влево, пока не встретит меньший. Большие элементы при этом сдвигаются на одно место вправо. На случайных данных это O(n²), а на почти отсортированных — почти O(n): отсортированному массиву нужно всего n−1 сравнений.
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.