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

Сортирующие сети

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

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

• Компаратор берёт два числа и отправляет меньшее вверх, а большее вниз.
• Сортирующая сеть это неизменная схема компараторов, которая сортирует любой вход.
• Компараторы на разных проводах могут работать одновременно: это параллелизм. 12 сравнений всего за 5 раундов.

Начать урок

Как идёт урок

1. Рисунок мелом и одно правило на каждом пересечении: меньшее идёт вверх. Может ли рисунок сортировать?

   Поставь четыре числа на входы в любом порядке, потом «Запуск».

2. Шесть проводов. Смотри раунд за раундом.

   «Шаг» запускает один раунд. Считай сравнения и раунды.

3. Попробуй её сломать.

   Перемешай входы кнопками обмена, потом «Запуск». Шесть попыток получить выход не по порядку.

4. Сортирующие сети.

   Компаратор берёт два числа и отправляет меньшее вверх, а большее вниз.

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

   Компараторы на разных проводах могут работать одновременно: параллелизм. Шесть чисел требуют 12 сравнений, но всего 5 раундов.

5. Эти компараторы нарисованы один за другим. Какие могут сработать вместе первыми?

   Нажми на них, потом «Проверить».

   Два компаратора могут работать одновременно, только если у них нет общего провода и ни одному не нужен результат, который другой ещё вычисляет.

6. Эта сеть потеряла компаратор.

   Запусти, посмотри, что выходит, потом добавь недостающий.

7. Построй свою сеть для 3 чисел.

   Три компаратора. Проверь все 6 порядков, потом «Проверить».

   После первых двух компараторов самое большое число столкнуто на провод 3. Последний компаратор сортирует верхние два.

8. Миллион сравнений. Сколько работников нужно, чтобы уложиться в 1000 тактов?

   Каждый работник делает одно сравнение за такт, все одновременно.

9. Твоя сеть на каждом входе.

   Пропусти все шесть порядков через построенную сеть.

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

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