TwiddleLab / Код / Алгоритмы в движении

Быстрая сортировка: выбери опорный

Урок 8 из 11 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Быстрая сортировка: выбери опорный элемент, отправь меньшие влево, а большие вправо, потом сделай то же с каждой стороной.
• Такое разделение называется разбиением. После него опорный стоит на своём окончательном месте.
• Опорный около середины (медиана) делит работу пополам: около n log n. Опорный с края, например первая карта отсортированного ряда, даёт n x n.

Начать урок

Как идёт урок

1. Отсортируй класс по росту за секунды. Выбери одного человека: кто ниже, влево, кто выше, вправо.

   Нажми на кого угодно, чтобы сделать его опорным.

2. Побудь разбиением. Опорный ростом 160 см.

   Перетащи каждого человека на сторону поменьше или побольше.

3. Теперь раздели, потом раздели части.

   Машина берёт первую карту каждой группы как опорную. Пройди по уровням.

4. Ряд уже отсортирован, а опорный по-прежнему первая карта.

   Какая картинка показывает его разделения? Нажми на одну, потом «Проверить».

   Если опорный самая маленькая карта, влево ничего не идёт, а всё остальное вправо, поэтому каждый уровень убирает всего одну карту. Это n - 1 + n - 2 + ... + 1: территория n x n.

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

   Быстрая сортировка: выбери опорный. Меньшие элементы влево, большие вправо: это разбиение. Теперь опорный на своём окончательном месте.

   Потом так же быстро отсортируй каждую сторону, пока в каждой группе не останется по одному элементу.

   Опорный около середины делит группы пополам: около n log n. Опорный с края отщипывает по одному элементу: n x n.

6. Напиши разбиение.

   Каждая карта после опорной идёт в smaller или bigger.

7. Какой опорный делит класс поровну?

   Двигай опорный по росту. «Проверить», когда разделение ровное.

   У медианы половина значений ниже и половина выше, поэтому она делит группу на две равные половины.

8. Выбор опорного.

   Четыре ряда. Нажми на опорный, который делит каждый ряд ровнее всего. Разделяет твоё разбиение.

9. В этом разбиении баг. Найди карту не на той стороне.

Предыдущий урок: Сортировка слиянием: слить и снова слить · Следующий урок: Сортирующие сети · Часть курса: Алгоритмы в движении

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.