Алхимик клана варит зелье и жалуется: пузырьки в котле всплывают строго по правилам.
Пузырёк умеет сравниться только с тем соседом, что прямо над ним, и, если тот легче,
они меняются местами. Никаких прыжков через полкотла — только сосед, только шаг.
Отсортируй массив по неубыванию методом пузырька: проходами по массиву, сравнивая
и обменивая только соседние элементы.
Входные данные
В первой строке — одно натуральное число N, не превосходящее 1000. Во второй строке — N целых чисел, не превосходящих по модулю 1000: веса пузырьков.
Выходные данные
Вывести получившийся массив — в одну строку через пробел.
Пример
Входные данные:
5
5 4 3 2 1
Выходные данные:
1 2 3 4 5
Ограничение. Встроенная сортировка запрещена: ни sort(), ни sorted(), ни чужая функция, которая сортирует за тебя. Проверяющий смотрит не на ответ, а на то, как ты его получил — правильный ответ неправильным методом здесь стоит меньше, чем аккуратный алгоритм.
Как это оценивается — 5 баллов
- Считаны N и все N чисел, дальше программа работает с массивом.
- Сравниваются только соседние элементы:
a[j] и a[j+1]. Сравнение через один — это уже другой алгоритм и другая задача.
- Если левый больше правого, они меняются местами — обменом, а не присваиванием в одну сторону.
- Проходов хватает, чтобы массив точно отсортировался: либо N − 1 проход, либо «пока был хотя бы один обмен». Индексы не выходят за правый край.
- Результат выведен одной строкой через пробел.
Минус. Внутренний цикл до range(n) вместо range(n-1) — и на последнем шаге программа тянется за элементом, которого нет. Массив короткий, ошибка длинная.