TwiddleLab / Курсы / Код

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

Устраивай гонки поисков и сортировок и смотри, почему одни алгоритмы растут гораздо быстрее других.

Средний уровень · уроков: 11 · Бесплатно, без аккаунта

Лучше после: Строим на Python, Рост: степени и логарифмы

Начать курс

Уроки

1. Считаем шаги (5 мин): Число шагов это сколько базовых шагов делает программа. Оно растёт вместе с размером данных n.
2. Линейный и двоичный поиск, ещё раз (7 мин): Линейный поиск проверяет элементы по одному: до n проверок.
3. Сортировка выбором (7 мин): Сортировка выбором: найди самое маленькое в неотсортированной части, поменяй его вперёд, повтори.
4. Сортировка вставками (7 мин): Сортировка вставками: возьми следующую карту и сдвигай её влево мимо каждой большей.
5. O большое: как растут столбики (7 мин): O большое называет, как число шагов растёт с n: O(1), O(log n), O(n), O(n²).
6. Слияние отсортированных стопок (7 мин): Чтобы слить две отсортированные стопки, сравнивай только две верхние карты; меньшая уходит.
7. Сортировка слиянием: слей и ещё раз слей (7 мин): Сортировка слиянием: одна карта уже отсортирована. Сливай пары, потом четвёрки, потом восьмёрки, пока не останется одна стопка.
8. Быстрая сортировка: выбери опорный (7 мин): Быстрая сортировка: выбери опорный элемент, отправь меньшие влево, а большие вправо, потом сделай то же с каждой стороной.
9. Сортирующие сети (7 мин): Компаратор берёт два числа и отправляет меньшее вверх, а большее вниз.
10. Жадный выбор (7 мин): Жадный алгоритм на каждом шаге берёт выбор, который выглядит лучшим, и никогда не оглядывается.
11. Гонка алгоритмов (7 мин): Бенчмарк устраивает гонку программ на одних данных, одного размера, с одним счётчиком.

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