Алгоритмы сортировки играют решающую роль в информатике, поскольку позволяют нам эффективно организовывать данные в различных приложениях. Одним из таких алгоритмов является сортировка вставками, известная своей простотой и эффективностью. В этой статье мы рассмотрим временную сложность сортировки вставкой и приведем примеры кода для различных реализаций.

Понимание сортировки вставками.
Сортировка вставками — это алгоритм сортировки на основе сравнения, который создает окончательный отсортированный массив по одному элементу за раз. Он работает путем разделения исходного несортированного массива на отсортированную и несортированную части. Алгоритм перебирает несортированную часть и выбирает каждый элемент, сравнивая его с элементами отсортированной части, чтобы найти его правильную позицию. Затем выбранный элемент вставляется в отсортированную часть, сдвигая при необходимости остальные элементы.

Временная сложность сортировки вставкой.
Чтобы проанализировать временную сложность сортировки вставкой, давайте рассмотрим наихудший сценарий, когда входной массив находится в обратном порядке. В этом случае каждый элемент необходимо сравнить со всеми предыдущими элементами в отсортированной части, что приводит к временной сложности O(n^2), где n — количество элементов в массиве.

Различные реализации сортировки вставками:

1. Базовая реализация:

   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

2. Рекурсивная реализация:

   def insertion_sort_recursive(arr, n):
      if n <= 1:
          return
      insertion_sort_recursive(arr, n - 1)
      key = arr[n - 1]
      j = n - 2
      while j >= 0 and arr[j] > key:
          arr[j + 1] = arr[j]
          j -= 1
      arr[j + 1] = key

3. Реализация двоичного поиска:

   def binary_search(arr, key, low, high):
      while low <= high:
          mid = (low + high) // 2
          if arr[mid] == key:
              return mid
          elif arr[mid] < key:
              low = mid + 1
          else:
              high = mid - 1
      return low
   def insertion_sort_binary_search(arr):
      for i in range(1, len(arr)):
          key = arr[i]
          j = i - 1
          index = binary_search(arr, key, 0, j)
          while j >= index:
              arr[j + 1] = arr[j]
              j -= 1
          arr[j + 1] = key

Сортировка вставками – это простой и эффективный алгоритм сортировки, особенно для входных данных небольшого размера или частично отсортированных массивов. Несмотря на то, что временная сложность наихудшего случая равна O(n^2), на практике он работает хорошо и может быть дополнительно оптимизирован с использованием таких методов, как двоичный поиск. Поняв и реализовав сортировку вставками, вы сможете глубже понять алгоритмы сортировки и их временную сложность.