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

Гонка алгоритмов

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

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

• Бенчмарк устраивает гонку программ на одних данных, одного размера, с одним счётчиком.
• Какая сортировка победит, зависит от трассы: вставки любят почти отсортированные данные, выбору всё равно, слияние побеждает при большом n.
• Меняй одно за раз, иначе гонка ничего не скажет. ИИ-модели сравнивают так же.

Начать урок

Как идёт урок

1. Какая сортировка побеждает? Зависит от трассы.

   Первая ставка: кто победит на почти отсортированной трассе?

2. Четыре трассы, два гонщика, по 20 чисел.

   Короткий столбик финиширует первым. Устрой гонку.

3. Меняй размер и трассу.

   Попробуй хотя бы три настройки.

4. Бенчмарки.

   Бенчмарк это гонка программ: одни данные, один размер, один способ счёта.

   Запускай на нескольких трассах: случайная, отсортированная, перевёрнутая, почти отсортированная. Одна трасса может спрятать слабость.

   Теперь собери своих гонщиков. У каждого есть счётчик steps.

5. Гонщик 1: сортировка вставками со счётчиком шагов.

   Один шаг на карту плюс один на сдвиг.

6. Гонщик 2: сортировка выбором со счётчиком шагов.

   Один шаг на сравнение.

7. Устрой гонку двух гонщиков на всех четырёх трассах.

   Твой код запускается по-настоящему, по 20 чисел на трассу.

8. Прочитай результаты: кто победил на каждой трассе?

   Нажми на победителя в каждой строке, потом «Проверить».

   На перевёрнутых данных каждая пара не по порядку, поэтому вставки делают все 190 сдвигов плюс 19 взглядов: 209 против 190 у выбора.

9. Кто-то выложил такую гонку: вставки разгромили выбор. Что не так?

   Нажимай на фишку трассы, чтобы менять данные этого гонщика, пока гонка не станет честной.

10. Испытание: когда сортировка слиянием берёт верх?

    Слияние против вставок на случайных данных. Найди наименьшее n, начиная с которого слияние побеждает. 5 тестов.

11. Сортировка вставками на перевёрнутом списке из 100. Сколько сдвигов?

    Каждый сдвиг исправляет ровно одну пару не по порядку. В перевёрнутом списке таких все 100 x 99 / 2 = 4950.

12. Моя гонка сортировок.

    Твоя таблица от твоих гонщиков. Нажми на трассу, чтобы повторить её.

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

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