Напишите программу, которая выполняет сортировку массива в порядке возрастания с использованием метода камня

Сортировка методом камня:

Инструкция:
Сортировка методом камня является модификацией метода пузырька. Она основана на том, что на каждой итерации самый "тяжелый" элемент, то есть элемент, который должен быть в конце отсортированного массива, опускается вниз.

Для решения этой задачи необходимо выполнить следующие шаги:

1. Считать размер массива n.
2. Считать элементы массива и сохранить их в массиве.
3. Организовать два вложенных цикла. Внешний цикл будет проходить по элементам массива слева направо, а внутренний цикл будет сравнивать текущий элемент с элементом справа. Если текущий элемент больше следующего элемента, то необходимо выполнить обмен местами.
4. После каждой перестановки элементов вывести весь массив.
5. Повторить шаги 3-4 до тех пор, пока массив не будет отсортирован.

Например:
Входные данные:
5
3 1 4 2 5

Шаги сортировки:
1 3 2 4 5
1 2 3 4 5

Совет:
Чтобы лучше понять и запомнить этот алгоритм, рекомендуется визуализировать его на бумаге или в программе для рисования. Проверьте свои решения на небольших примерах и постепенно переходите к более сложным задачам.

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

Входные данные:
8
5 8 2 6 1 3 7 4

Ожидаемый результат:
1 2 3 4 5 6 7 8