Как ответить
Внешний цикл в 11-й строке отвечает за проход по всем элементам массива, которые ещё не находятся на своих финальных позициях. В контексте пузырьковой сортировки (bubble sort) этот цикл гарантирует, что после каждого полного прохода внутреннего цикла самый большой элемент «всплывает» в конец неотсортированной части массива.
Вот как это работает на конкретном примере. Допустим, у нас есть массив [5, 3, 8, 1]. Внешний цикл выполнится 4 раза (по количеству элементов).
- Первая итерация внешнего цикла: Внутренний цикл проходит от начала до конца, сравнивает соседние элементы и меняет их местами, если левый больше правого. После этого прохода число 8 оказывается в конце:
[3, 5, 1, 8]. - Вторая итерация: Внутренний цикл теперь может не проверять последний элемент (он уже на месте). После прохода число 5 встаёт на предпоследнее место:
[3, 1, 5, 8]. - Третья итерация: Число 3 встаёт на своё место:
[1, 3, 5, 8]. - Четвёртая итерация: Формально нужна, чтобы убедиться, что массив отсортирован, хотя на практике можно добавить проверку на отсутствие перестановок и выйти раньше.
Ключевой момент: количество итераций внешнего цикла равно n - 1, где n — длина массива. Это минимум, необходимый для гарантии полной сортировки. Если убрать внешний цикл, внутренний выполнится только один раз — массив останется неотсортированным, потому что самый большой элемент уйдёт в конец, но остальные останутся на своих местах.
В более сложных алгоритмах, например, в сортировке вставками, внешний цикл выполняет ту же роль — перебирает все элементы, которые нужно вставить в уже отсортированную часть. Разница только в том, что в пузырьковой сортировке внешний цикл отвечает за «количество проходов», а во вставках — за «выбор текущего элемента для вставки».
На собеседовании стоит упомянуть, что внешний цикл можно оптимизировать: если за весь проход не было ни одной перестановки, массив уже отсортирован, и можно завершить внешний цикл досрочно. Это улучшает среднее время работы с O(n²) до O(n) для уже отсортированных данных.