Сортировка вставками с использованием цикла For: алгоритм и реализация

Чтобы реализовать сортировку вставкой с помощью цикла for, вы можете выполнить следующие действия:

  1. Начните со второго элемента массива (при условии, что первый элемент уже отсортирован).
  2. Перебрать оставшиеся элементы массива.
  3. Для каждого элемента сравните его с элементами слева от него.
  4. Если элемент меньше элемента слева от него, поменяйте их местами.
  5. Продолжайте замену, пока элемент не займет правильную отсортированную позицию.
  6. Повторите шаги 2–5 для всех остальных элементов массива.

Вот пример реализации на Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Эта реализация использует цикл for для перебора каждого элемента и цикл while для процесса замены. Временная сложность сортировки вставками в худшем случае составляет O(n^2).