Сортировка вставками (Insertion Sort)

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

Принцип работы

Алгоритм сортировки вставками работает следующим образом:

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

Пример

Пусть у нас есть следующий список: [5, 1, 4, 2, 8]

1. Первый проход:
   1. (5, 1, 4, 2, 8) → (1, 5, 4, 2, 8) (1 вставляется перед 5)
2. Второй проход:
   1. (1, 5, 4, 2, 8) → (1, 4, 5, 2, 8) (4 вставляется между 1 и 5)
3. Третий проход:
   1. (1, 4, 5, 2, 8) → (1, 2, 4, 5, 8) (2 вставляется между 1 и 4)
4. Четвертый проход:
   1. (1, 2, 4, 5, 8) → (1, 2, 4, 5, 8) (8 остается на месте, так как он больше 5)

В результате список отсортирован: [1, 2, 4, 5, 8]

Реализация на Python

<syntaxhighlight lang="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

1. Пример использования

arr = [5, 1, 4, 2, 8] sorted_arr = insertion_sort(arr) print(sorted_arr) # Вывод: [1, 2, 4, 5, 8] </syntaxhighlight>

Характеристики

• Простота: Легко понять и реализовать.
• Эффективность для небольших наборов данных: Хорошо работает для небольших списков.
• Эффективность для частично отсортированных списков: Хорошо работает для списков, которые почти отсортированы.
• Сложность:
  • Временная сложность:
    • Лучший случай: O(n) (если список уже отсортирован)
    • Средний случай: O(n^2)
    • Худший случай: O(n^2)
  • Пространственная сложность: O(1) (не требует дополнительной памяти)
• Устойчивость: Сортировка вставками является устойчивым алгоритмом.

Когда использовать

• Для небольших наборов данных.
• Когда список почти отсортирован.
• Когда нужна простая и легко реализуемая сортировка.

Преимущества

• Простая реализация.
• Эффективна для небольших наборов данных.
• Эффективна для частично отсортированных списков.
• Не требует дополнительной памяти.
• Устойчивый алгоритм.

Недостатки

• Неэффективна для больших наборов данных.
• Квадратичная временная сложность в среднем и худшем случаях.