Сортировка вставками

Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:

• эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
• эффективен на наборах данных, которые уже частично отсортированы;
• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
• может сортировать список по мере его получения;
• использует O(1) временной памяти, включая стек.

Минусом же является высокая сложность алгоритма: O(n²).

Описание

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.

Анализ алгоритма

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — θ(n²).

Псевдокод

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n]

for i = 2, 3, ..., n:  
    key := A[i]
    j := i - 1
    while j > 0 and A[j] > key:
        A[j + 1] := A[j]
        j := j - 1
    A[j + 1] := key

Реализация на Java/C/С++

void insertSort(int a[], int size)
{
    int i, j, tmp;
    for (i = 0; i < size; i++)
    {
        tmp = a[i];
        for (j = i - 1; j >= 0 && a[j] > tmp; j--)
            a[j + 1] = a[j];
        a[j + 1] = tmp;
    }
}

Ссылки

• Сортировка вставками
• Анимированное представление алгоритма сортировки вставками