TwiddleLab / Код / Как думает программист

Сортировка по одному обмену

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

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

• Сортировка расставляет список по порядку. Пузырьковая сортировка сравнивает соседей и меняет их местами, если они стоят не по порядку.
• Один проход идёт по списку один раз слева направо. Самое большое значение всегда оказывается в конце.
• Чтобы поменять два значения местами, нужна запасная коробка temp, как в головоломке с обменом.
• Каждый обмен исправляет одну пару не по порядку, поэтому перевёрнутый список требует больше всего работы.

Начать урок

Как идёт урок

1. Восемь столбиков, высоты случайные.

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

2. Игра: отсортируй столбики, меняя только соседей.

   От самого низкого к самому высокому, слева направо. Уложись в норму, и будет три звезды.

3. Теперь один проход делает компьютер.

   Нажми «Шаг». Оранжевая рамка: обмен. Зелёная: уже по порядку.

4. У всего этого есть имена.

   Сортировка расставляет список по порядку. Способов много.

   Пузырьковая сортировка сравнивает соседей и меняет их местами, если они стоят не по порядку. Большие значения всплывают в конец.

   Один проход по списку это проход. Повторяй проходы, пока обменов не останется, и список отсортирован.

   Для обмена нужна запасная коробка temp, как в твоей головоломке с обменом. Смотри, как она меняет местами 5 и 2.

5. Напиши один проход пузырьковой сортировки.

   Расставь строки по порядку и нажми «Запуск». Одна строка ловушка.

6. Предскажи обмены.

   Нажми на каждый промежуток, где за один проход будет обмен. Осторожно: обменянный столбик продолжает двигаться.

7. Лента должна показывать лучшие посты первыми.

   Этот код сортирует оценки постов, но худший пост оказывается наверху. Поменяй один символ и нажми «Запуск».

8. Построй список, который пузырьковая сортировка ненавидит больше всего.

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

9. Сколько обменов нужно пузырьковой сортировке для твоего списка?

10. Гонка: твой самый трудный список против почти отсортированного.

    Тот же алгоритм, та же скорость. Нажми «Старт».

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

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