Сортировка вставкой работает так же, как многие люди сортируют руки игральных карт.
Пояснение к алгоритму:
- Мы начнем с итерации массива со второй позиции.
- Мы создадим ключевую переменную, которая будет значением, которое мы хотим отсортировать во время цикла j.
- Мы создадим другую переменную i, которая будет индексом перед текущим индексом (из-за этого мы начинаем со второго значения массива)
- Теперь мы выполним цикл, пока i находится на границе массива, а значение в позиции i больше, чем значение ключа.
- Если мы войдем в цикл, мы заменим значение, находящееся в i + 1, на значение, которое находится в i. Итак, мы собираемся уменьшить на одну единицу в i.
- Когда мы заканчиваем цикл, мы присваиваем значению, которое находится в позиции i + 1, значение ключа.
- Когда for завершается, мы возвращаем упорядоченный массив.
Упражнение:
- Напишите алгоритм сортировки вставкой, чтобы упорядочить массив по убыванию.
Отвечать:
Чтобы порядок был убывающим, просто измените знак с «больше» на «меньше» в while.