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

Сортировка выбором

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

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

• Сортировка выбором: найди самое маленькое в неотсортированной части, поменяй его вперёд, повтори.
• Отсортированное начало растёт на один за проход, как стена, которая движется вправо.
• На n элементах она делает (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 сравнений: 28 для 8, 4950 для 100.
• Она делает столько же, даже когда список уже отсортирован.

Начать урок

Как идёт урок

1. Отсортируй плейлист по длине: найди самую короткую песню, поставь её первой, повтори.

   Найти самую короткую значит сравнивать песни. Сколько сравнений нужно, чтобы отсортировать все 8?

2. Отсортируй вручную. Нажми на самую короткую песню справа от стены.

   Счётчик добавляет каждое сравнение, которое нужно сортировке, чтобы быть уверенной.

3. Теперь смотри, как это делает машина, по одному сравнению.

   «Шаг», «Проход» или «Запуск». Смотри на лесенку справа.

4. Сортировка выбором.

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

   Левая часть это отсортированное начало. Оно растёт на один элемент каждый проход и больше не меняется.

   На n элементах: (n - 1) + (n - 2) + ... + 1 сравнений. Для 8 элементов это 28.

5. Напиши сортировку выбором со счётчиком сравнений.

   best это индекс самого маленького пока. Меняй местами через t, запасную коробку.

6. Покажи список после 3 проходов сортировки выбором.

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

   Каждый проход меняет местами всего два столбика: самый маленький в неотсортированной части и столбик в её начале. Поэтому после 3 проходов на местах только первые 3.

7. 100 песен. Сколько сравнений?

   99 + 98 + ... + 1. Квадрат пар даёт короткий путь.

   Сравнения это все пары разных песен, каждая по разу: n x n клеток, минус n на диагонали, пополам. 100 x 99 / 2 = 4950.

8. Спринт сортировки.

   Три списка, всё длиннее. Каждый раз нажимай на самое маленькое. Быстро и без промахов.

9. Твоя сортировка выбором встречает уже отсортированный список.

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

   Внутренний цикл идёт для j от i + 1 до конца, какими бы ни были значения. Число зависит только от n, а не от порядка.

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

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