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

Сортировка слиянием: слей и ещё раз слей

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

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

• Сортировка слиянием: одна карта уже отсортирована. Сливай пары, потом четвёрки, потом восьмёрки, пока не останется одна стопка.
• Раундов log₂ n, и каждый раунд двигает каждую карту один раз: около n log n шагов.
• Для миллиона элементов: около 20 миллионов шагов против примерно 500 миллиардов у сортировки выбором.

Начать урок

Как идёт урок

1. Сортировка выбором на миллионе элементов: около 500 миллиардов сравнений. Может ли слияние лучше?

   Сортировка слиянием только и делает, что сливает. Поставь, сколько шагов ей нужно на миллион.

2. Раздай себе 8 карт, потом разрежь их до отдельных карт.

   Выбери любые 8. Потом нажимай на стопку, чтобы разрезать её пополам, пока каждая стопка не станет одной картой.

3. Теперь слей руку обратно. Машина делает пары и четвёрки; последний раунд твой.

   Тяни меньшую верхнюю карту, как в прошлом уроке.

4. 16 карт. Посчитай раунды и работу в каждом.

   Нажимай «Раунд слияния», пока не останется одна стопка.

5. Сортировка слиянием.

   Сортировка слиянием: начни со стопок из одной карты. Сливай соседей в двойки, потом четвёрки, потом восьмёрки, пока не останется одна стопка.

   Число раундов log₂ n: сколько раз n делится пополам до 1. Каждый раунд двигает каждую карту один раз: работа n.

   Итого около n log n. Миллион элементов: 20 раундов по миллиону, около 20 миллионов шагов.

6. Сколько карт дают башню из 10 уровней?

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

   Каждый раунд вдвое уменьшает число стопок. Из 1024 стопок по одной карте нужно 10 делений пополам, чтобы дойти до 1 стопки.

7. Покажи список после 2 раундов сортировки слиянием.

   Каждая группа из 4 отсортирована внутри. Перетаскивай столбики, чтобы менять их, потом «Проверить».

   После раунда k каждая группа из 2ᵏ соседей отсортирована внутри, но группы ещё не встретились.

8. 1 048 576 элементов. Какой план уложится в минуту?

   Миллион шагов в секунду. Нажми на план, потом «Проверить».

   n log₂ n = 1 048 576 x 20 ≈ 21 миллион. n² = 1 048 576² ≈ 1,1 триллиона. При миллионе в секунду: 21 с против примерно 12,7 дня.

9. Обгони прожектор.

   32 карты. Сортировка выбором стартует вместе с тобой. Нажми «Раунд слияния» 5 раз, быстро.

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

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