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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Сортировка вставками
Пример сортировки вставками случайных чисел

Иллюстрация сортировки вставками
Предназначение

Алгоритм сортировки

Структура данных

Массив

Худшее время

О(n2) сравнений, обменов

Лучшее время

O(n) сравнений, O(1) обмен

Среднее время

О(n2) сравнений, обменов

Затраты памяти

О(n) всего, O(1) вспомогательный

Пример сортировки вставками

Сортировка вставками — примитивный алгоритм сортировки с высокой вычислительной сложностью: O(n^2).

Плюсы:

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

Минусы:

Описание[править | править вики-текст]

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

Анализ алгоритма[править | править вики-текст]

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

Псевдокод[править | править вики-текст]

На псевдокоде[1]:

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

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

Примечания[править | править вики-текст]

  1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 2.1. Сортировка вставкой // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 57-64. — ISBN 5-8459-0857-4.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]