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

Сортировка вставками - это простой алгоритм сортировки, который строит отсортированный массив (или список), вставляя каждый новый элемент в уже отсортированную последовательность.

Алгоритм

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

1. Начинаем с первого элемента массива, считая его уже отсортированным.
2. Берем следующий элемент и сравниваем его с элементами в отсортированной части массива.
3. Вставляем этот элемент в правильное место в отсортированной части.
4. Повторяем процесс для всех элементов.

Анализ сложности

• Временная сложность сортировки вставками: В худшем случае $O(n^2)$, где $n$ - количество элементов. В лучшем случае - $O(n)$, если массив уже отсортирован.
• Пространственная сложность сортировки вставками: $O(1)$, так как сортировка происходит "на месте" без использования дополнительных структур данных.

Реализация

Приведём примеры реализации сортировки вставками:

Python

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

C++

#include <vector>

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Java

public void insertionSort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Заключение

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

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