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