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