Сортировка вставкой работает так же, как многие люди сортируют руки игральных карт.

Пояснение к алгоритму:

  1. Мы начнем с итерации массива со второй позиции.
  2. Мы создадим ключевую переменную, которая будет значением, которое мы хотим отсортировать во время цикла j.
  3. Мы создадим другую переменную i, которая будет индексом перед текущим индексом (из-за этого мы начинаем со второго значения массива)
  4. Теперь мы выполним цикл, пока i находится на границе массива, а значение в позиции i больше, чем значение ключа.
  5. Если мы войдем в цикл, мы заменим значение, находящееся в i + 1, на значение, которое находится в i. Итак, мы собираемся уменьшить на одну единицу в i.
  6. Когда мы заканчиваем цикл, мы присваиваем значению, которое находится в позиции i + 1, значение ключа.
  7. Когда for завершается, мы возвращаем упорядоченный массив.

Упражнение:

  1. Напишите алгоритм сортировки вставкой, чтобы упорядочить массив по убыванию.

Отвечать:

Чтобы порядок был убывающим, просто измените знак с «больше» на «меньше» в while.