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

Сортировка вставками

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

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

• Сортировка вставками: возьми следующую карту и сдвигай её влево мимо каждой большей.
• Каждый сдвиг исправляет одну пару не по порядку, поэтому работа зависит от данных.
• Лучший случай: уже отсортировано, сдвигов нет, около n сравнений. Худший случай: перевёрнуто, сдвигается каждая пара, n(n - 1)/2.
• Почти отсортированные данные, вроде ленты с рейтингом и парой новых постов, это место, где сортировка вставками блистает.

Начать урок

Как идёт урок

1. Берёшь карты по одной и держишь руку отсортированной.

   Две руки для сортировки. Какой понадобится меньше ходов?

2. Отсортируй руку так, как это делает мозг.

   Тяни оранжевую карту влево на её место. Зелёные карты уже по порядку.

3. Сделай руку, которая стоит ровно 10 сдвигов.

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

   Сдвиг меняет местами двух соседей, стоящих не по порядку, и это исправляет ровно одну такую пару. Поэтому число сдвигов равно числу пар не по порядку.

4. Сортировка вставками.

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

   Работа зависит от данных. Лучший случай: уже отсортировано, сдвигов нет, n - 1 сравнений.

   Худший случай: перевёрнуто, сдвигается каждая пара: n(n - 1)/2, так же медленно, как сортировка выбором. Почти отсортированные данные почти так же дёшевы, как лучший случай.

5. Та же идея на Python. Пройди по шагам.

   Смотри, как j сдвигается влево, пока карта перед ним больше.

6. Собери сдвиг.

   Цикл готов. Добавь строки, которые сдвигают карту j влево.

7. Живая лента: новые посты всё приходят.

   Лента отсортирована по рейтингу, сверху самый высокий. Вставь каждый новый пост на место, пока полоска не кончилась.

8. Быстро или медленно для сортировки вставками?

   Посчитай пары не по порядку. Перетащи каждый список в банку.

9. Куда встанет оранжевая карта?

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

   Цикл продолжает менять, пока карта перед ней больше. 9, 7 и 5 больше 4; 2 нет, поэтому она там останавливается.

10. Гонка: выбор против вставок.

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

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

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