Просмотр исходного текста страницы Сортировка вставками (Insertion Sort)

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

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

== Пример ==
Пусть у нас есть следующий список: <code>[5, 1, 4, 2, 8]</code>
# '''Первый проход:'''
## <code>(5, 1, 4, 2, 8)</code> → <code>(1, 5, 4, 2, 8)</code> (1 вставляется перед 5)
# '''Второй проход:'''
## <code>(1, 5, 4, 2, 8)</code> → <code>(1, 4, 5, 2, 8)</code> (4 вставляется между 1 и 5)
# '''Третий проход:'''
## <code>(1, 4, 5, 2, 8)</code> → <code>(1, 2, 4, 5, 8)</code> (2 вставляется между 1 и 4)
# '''Четвертый проход:'''
## <code>(1, 2, 4, 5, 8)</code> → <code>(1, 2, 4, 5, 8)</code> (8 остается на месте, так как он больше 5)
В результате список отсортирован: <code>[1, 2, 4, 5, 8]</code>

== Реализация на 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

# Пример использования
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) (не требует дополнительной памяти)
* '''Устойчивость:''' Сортировка вставками является устойчивым алгоритмом.

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

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

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