Условие
Дан массив из n целых чисел. Отсортируйте его по неубыванию методом пузырьковой сортировки: последовательно сравнивайте соседние элементы и меняйте их местами, если они расположены в неправильном порядке. Повторяйте проходы, пока массив не будет отсортирован.
Реализуйте сортировку в отдельной функции void bubble_sort(int array[], int n). Функция должна изменять переданный массив и не выполнять ввод или вывод. В функции main прочитайте массив, вызовите bubble_sort и выведите результат. Использование готовых функций сортировки, включая qsort и std::sort, запрещено.
Материал к заданию
Основные виды сортировок и примеры их реализации — Яндекс Образование, раздел «Пузырьковая сортировка и её улучшения». Реализацию из статьи адаптируйте к массиву и интерфейсу bubble_sort, заданным в условии.
Сложность алгоритмов. Разбор Big O — Хабр — материал об асимптотической оценке сложности алгоритмов.
Ограничения
Время: 2 секунды. Память: 64 МиБ. Вывод: до 2 МиБ. Стандарты: C11 / C++17.
Входные данные
В первой строке вводится целое число n — количество элементов массива. Во второй строке вводятся n целых чисел, разделённых пробелами. Ограничения: 1 ≤ n ≤ 1000, −10⁹ ≤ aᵢ ≤ 10⁹. Значения могут повторяться; массив может быть уже отсортирован или расположен в обратном порядке.
Выходные данные
Выведите n элементов отсортированного массива в одной строке через пробел. Каждый следующий элемент должен быть не меньше предыдущего. Все исходные элементы, включая повторяющиеся значения, должны сохраниться.
Примеры
5 3 -1 3 0 2
-1 0 2 3 3
4 1 2 3 4
1 2 3 4
4 4 3 2 1
1 2 3 4