Как отсортировать массив по неубыванию методом вставок ? Вводится одно натуральное число, не превосходящее 1000

Сортировка методом вставок

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

Доп. материал:
Входные данные:
5
5 4 3 2 1

Шаг 1: 5 4 3 2 1 (начальный массив)

Шаг 2: 4 5 3 2 1 (поменяли местами 5 и 4)

Шаг 3: 4 3 5 2 1 (поменяли местами 5 и 3)

Шаг 4: 3 4 5 2 1 (поменяли местами 4 и 3)

Шаг 5: 3 4 2 5 1 (поменяли местами 5 и 2)

Шаг 6: 3 2 4 5 1 (поменяли местами 4 и 2)

Шаг 7: 2 3 4 5 1 (поменяли местами 3 и 2)

Шаг 8: 2 3 4 1 5 (поменяли местами 5 и 1)

Шаг 9: 2 3 1 4 5 (поменяли местами 4 и 1)

Шаг 10: 2 1 3 4 5 (поменяли местами 3 и 1)

Шаг 11: 1 2 3 4 5 (поменяли местами 2 и 1)

Выходные данные: 1 2 3 4 5 (отсортированный массив)

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

Задание для закрепления: Отсортируйте массив [8, 1, 6, 3, 5] методом вставок. Введите получившийся отсортированный массив.