Сравнения
Обмены
Разбиения

  • Разбиваемая часть
  • Опорный элемент
  • Сравниваются
  • Обменяны
  • На месте

Подробнее о быстрой сортировке

Быстрая сортировка

Быстрая сортировка выбирает опорный элемент, ставит все меньшие значения перед ним, а все остальные после него, и затем так же сортирует обе стороны. После каждого разбиения опорный элемент оказывается на своём окончательном месте. Задайте, как выбирается опорный элемент, запустите сортировку с любой скоростью или проходите её по одному сравнению и посмотрите, почему плохой опорный элемент на отсортированном списке делает быструю сортировку медленной. Нажмите «Пуск», чтобы посмотреть сортировку, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Плитки считают сравнения, обмены и разбиения. Выберите число столбиков, начальный порядок или введите свои числа, а также способ выбора опорного элемента. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

Как это работает

  1. Выберите число столбиков и начальный порядок: случайный, почти отсортированный, обратный или с небольшим числом разных значений. Или введите свои числа.
  2. Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место сортировки.
  3. Выберите правило для опорного элемента: последнее значение, значение из середины, случайное значение или медиана трёх. Попробуйте каждое на отсортированном списке.

Как работает быстрая сортировка

Выберите одно значение сортируемой части в качестве опорного и перенесите его в конец. Пройдите по остальным значениям слева направо; каждое значение меньше опорного обменом попадает в левую часть, которая растёт от начала. Затем обменом поставьте опорный элемент сразу за левой частью. Всё перед ним теперь меньше, а после него — нет, так что опорный элемент стоит на своём окончательном месте. Так же отсортируйте часть перед ним и часть после него, пока каждая часть не станет одним значением.

Почему важен опорный элемент

Когда опорный элемент оказывается ближе к середине, каждое разбиение делит задачу пополам, и число сравнений растёт как n log n: для 40 случайных значений около 190. Когда опорный элемент — наименьшее или наибольшее значение, одна сторона пуста, а в другой всё остальное. Если опорный элемент — последнее значение, на отсортированном или обратном списке так происходит на каждом шаге, и сортировка требует n(n − 1)/2 сравнений, 780 для 40 значений. Случайный опорный элемент или медиана первого, среднего и последнего значений на практике этого избегают.

Часто задаваемые вопросы

Как работает быстрая сортировка?

Она выбирает опорный элемент, разбивает список так, чтобы меньшие значения оказались перед опорным, а остальные после него, и затем сортирует обе стороны быстрой сортировкой. После каждого разбиения опорный элемент стоит на своём окончательном месте.

Почему быстрая сортировка медленна на отсортированном списке?

Если опорный элемент — первое или последнее значение, отсортированный список всегда даёт в качестве опорного наименьшее или наибольшее значение. Тогда одна сторона разбиения пуста, каждое разбиение убирает только одно значение, и сортировка требует n(n − 1)/2 сравнений. Случайный опорный элемент или медиана трёх на практике это исправляют.

Быстрая сортировка быстрее сортировки слиянием?

На практике часто да: она сортирует на месте, не требует буфера, а её внутренний цикл очень прост. В среднем она делает чуть больше сравнений, чем сортировка слиянием, и её худший случай — n², тогда как у сортировки слиянием всегда n log n. Библиотечные сортировки, например introsort, начинают с быстрой сортировки и переходят на пирамидальную, если разбиения становятся слишком неравными.

Устойчива ли быстрая сортировка?

Нет. Разбиение переставляет значения на большие расстояния, поэтому равные значения могут поменять порядок.

Мои числа куда-нибудь отправляются?

Нет. Сортировка работает в вашем браузере, а последние настройки остаются в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор