Сколько обменов сделает сортировка пузырьком для массива 7 3 9 1 5

Решение по шагам

1. 1

   Шаг 1. Разбираемся, как устроен один проход

   Проход — это движение слева направо по всем парам соседей. На каждом шаге мы смотрим ровно на два стоящих рядом элемента и меняем их местами, если левый больше правого. Ни минимума, ни максимума по всему массиву при этом не ищут — сравниваются только соседи.

   В массиве из 5 элементов пар соседей четыре: (1,2), (2,3), (3,4), (4,5). Значит, в каждом проходе будет ровно 4 сравнения.

   Сделаем первые два шага первого прохода:

   • сравниваем 7 и 3: левый больше — меняем местами, массив становится 3 7 9 1 5;
   • сравниваем 7 и 9 (это уже новая пара соседей, на второй и третьей позициях): порядок правильный — обмена нет.
2. 2

   Шаг 2. Что именно считаем и когда остановимся

   Важно не путать две величины: сравнений в каждом проходе ровно 4, а обменов может быть от 0 до 4. В задаче спрашивают именно обмены, поэтому будем считать их отдельно по каждому проходу, а в конце сложим.

   Полезное свойство метода: за один проход наибольший из ещё неупорядоченных элементов обязательно «всплывает» в конец массива — отсюда и название. Поэтому для $n$ элементов содержательных проходов не больше $n - 1 = 4$.

   Остановка по условию задачи наступает не тогда, когда массив стал упорядоченным, а тогда, когда очередной проход прошёл без единого обмена. Такой контрольный проход обязательно выполняется, но обменов в общую сумму не добавляет.